## [Discrete Optimization Note] 1. Why optimization?

This is my note for

Discrete Optimizationin Coursera (https://class.coursera.org/optimization-002)

## Optimization Problems

- Filling a knapsack is an optimization problem.
- Optimization applications are among the most difficult problems in computer science.
- There are some examples:
- supply chains
- sport scheduling
- logistics
- electrical power system
- manufacturing

- They are incredibly hard to solve, but we need to solve them at all.

## NP-Completeness

- Complexity class for decision problems, e.g., "can I fill a knapsack for a value above K?"
- Informally, NP-Complet problems have two properties:
- We can check a solution quickly, i.e., in polynomial time
- If we can solve one NP-Complete quickly, then we're able to solve all NP-Complete problem quickly as well.

- As the input of problem increased, the required solving time is exponentially increasing.
- 解法思路：We try to push the complexity time exponential curve toward bigger n, so that we can actually solve practical problem for small n. 想辦法把T(n)的指數成長區段往更大的n推進，使得當n小的時候仍然可以用polynomial time找出解。
- 可行方案是降低最佳解的標準，找到近似最佳化條件的解法。

## Different techniques

**The purpose of all the following techniques is trying to pull the exponential or find the high quality solutions quickly.**

- Constraint programming
- Local searching
- Integer programming