3. Branch and Bound

3.1. Theory

3.2. Exercises

3.2.1. Knapsack Problem

Given the following knapsack instance:

\[\begin{split}\max \quad & 25 x_1 + 18 x_2 + 36 x_3 \\ \text{subject to} \quad & 5 x_1 + 6 x_2 + 4 x_3 \leq 11 \\ & x_i \in \{0, 1\}\end{split}\]

  1. Draw the brute-force search tree for this problem, with the given variable ordering and left (resp. right) corresponding to 0 (resp. 1) assignments.

  2. Compute the linear relaxation of the problem at each search node.

  3. What nodes can be pruned if we use this relaxation as a bounding procedure and traverse the search tree starting with the left-children? And if we traverse the search tree starting with the right-children?

  4. Do the same exercise but with the variable ordering \(x_3, x_1, x_2\). Did the performances change? Why?