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