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

Comments

comments powered by Disqus