[Discrete Optimization Note] 1. Why optimization?
This is my note for Discrete Optimization in 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