This is my note for Discrete Optimization in Coursera (https://class.coursera.org/optimization-002)
- 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
- electrical power system
- They are incredibly hard to solve, but we need to solve them at all.
- 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找出解。
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