白昌永（大白）

This is my note for Discrete Optimization in Coursera (https://class.coursera.org/optimization-002)

---

Greedy Algorithm Intuition

What is Greedy? Build a solution by picking itmes one at a time in greedy fasion.

Idea 1: more items are best.

Start with small ones and take as many as you can.

Idea 2: valuable items are best.

Start with the most valuable items.

Idea 3: value density!

Calculate dollars per kilogram.

---

Greedy Algorithm

• For one problem, there are many possible greddy algorithms. Some will do better than others. (Take a look at above ideas)
• Idea: Take the most valuable items first. And the next valuable item that can fit into a knapsack.
• Advantages:
  1. Quick to design and implement the algorithm.
  2. It can be very fast to model the problem.
• Problems:
  1. No quality guarantees (in general). You don't know much you can improve the algorithm, you don't know how good they are.
  2. Quality can vary widely on the input.

Summary of Greedy Algorithm:

Try to understand what the problem is. Get a base line, that's what you have to improve and then afterwards you going to use some of the techniques that we will present:

• Constraint Programming
• Local Searching
• Mixed Integer Programming To improve the greedy algorithm and find out how much you can improve.

---

Modeling

How to formalize an optimization task as a mathematical model. This is the key to solve the optimal problem.

How to model an optimization problem

1. Describe the problem
2. Choose some decision variables
3. Express the problem constraints in term of there variables
4. Express the objective function ( the quality of the solution )
5. There may be many ways to model an optimization problem.

Modeling the knapsack problem

1. Describe the problem:
   • For each i in Item, has weight Wi and value Vi.
   • We have a knapsack which capacity is K.
   • We have to find the subset of Item which value is maximum and summation of weight is less than or equal to K.
2. Choose some decision variables:
   • Xi is item i is selected or not
3. Express the problem constraints in term of there variables: $$\left( \sum_{i=Item}^n W_i X_i \right ) \leq K$$
4. Express the objective function ( the quality of the solution ) $$\left(\sum_{i=Item}^n V_i X_i \right )$$ is maximum and be subject to $$\left(\sum_{i=Item}^n W_i X_i \right ) \leq K$$
5. There may be many ways to model an optimization problem.

---

Dynamic Programming

Basic Principle:

• divide and conquer
• bottom up computation

Define the problem:

• Item selection I = { 1, 2, 3 ...... n }
• O( k, j ) is the optimal solution of capacity K of Item[ 1 ... j ] s.t.

maximize

$$\left(\sum_{x=1}^j V_i X_i \right )$$

and subject to

$$\left(\sum_{i=1}^j W_i X_i \right ) \leq K$$

Recurrence relation

• Before we want to solve O( k, j ), we solve sub-problemO( k, j - 1 ) first.

  O( k, j ) = max( O( k, j - 1 ), O( k - Wj, j - 1 ) + Vj ) if Wj <= K    // 第一個是不拿j, 第二個是拿j
  O( k, j ) = O( k, j - 1 ) if Wj > K  // 超重不拿j
  O( k, 0 ) = 0   // 什麼都不拿，價值就為零。