Branch-and-Bound 0/1 Knapsack

1. 0/1 KnapsackProblem
2. All approaches for 0/1 Knapsack Problem:
3. Brute-Force Search or Exhaustive Search: 2n
4. The 0/1 Knapsack Problem
5. e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.
6. Relax the Restriction
7. Upper Bound and Lower Bound
8. Relax the Restriction
9. e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.
10. Relax the Restriction
11. Upper Bound and Lower Bound
12. e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.
13. Expand the node with the best lower bound.

1/13

Volume

00:00/38:55

00:00/00:09

1. 0/1 KnapsackProblem
2. All approaches for 0/1 Knapsack Problem:
3. Brute-Force Search or Exhaustive Search: 2n
4. The 0/1 Knapsack Problem
5. e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.
6. Relax the Restriction
7. Upper Bound and Lower Bound
8. Relax the Restriction
9. e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.
10. Relax the Restriction
11. Upper Bound and Lower Bound
12. e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.
13. Expand the node with the best lower bound.