Branch and Bound
Interactive visualizations for Chapter 6 of the Ricerca Operativa notes
The Knapsack ILP
We work with the same knapsack instance used throughout Chapters 3 and 6 of the notes. There are 6 items, each with a weight and a value, and a knapsack with capacity \(W = 15\).
\[ \begin{aligned} & \text{maximize} && \sum_{j=1}^{6} v_j\, x_j = 8x_1 + 5x_2 + 11x_3 + 6x_4 + 4x_5 + 9x_6 \\ & \text{subject to} && \sum_{j=1}^{6} w_j\, x_j = 5x_1 + 3x_2 + 7x_3 + 4x_4 + 2x_5 + 6x_6 \leq 15 \\ & && x_j \in \{0, 1\}, \quad j = 1, \ldots, 6. \end{aligned} \]
| Item | Weight \(w_j\) | Value \(v_j\) | Ratio \(v_j/w_j\) |
|---|---|---|---|
| 1 | 5 | 8 | 1.60 |
| 2 | 3 | 5 | 1.67 |
| 3 | 7 | 11 | 1.57 |
| 4 | 4 | 6 | 1.50 |
| 5 | 2 | 4 | 2.00 |
| 6 | 6 | 9 | 1.50 |
The ILP optimum is \(z^*_{\mathrm{ILP}} = 24\), achieved by selecting items \(\{1, 2, 3\}\) (total weight \(5+3+7=15\), total value \(8+5+11=24\)).
LP Relaxation Bound
The LP relaxation replaces each \(x_j \in \{0,1\}\) with \(0 \leq x_j \leq 1\). It can be solved greedily: sort items by value/weight ratio in decreasing order and fill the knapsack until it is full, allowing the last item to be taken fractionally.
Sorted order by ratio: item 5 (2.00), item 2 (1.67), item 1 (1.60), item 3 (1.57), item 4 (1.50), item 6 (1.50).
Filling greedily:
- Take item 5 fully: weight used = 2, value = 4
- Take item 2 fully: weight used = 5, value = 9
- Take item 1 fully: weight used = 10, value = 17
- Take item 3 fractionally at \(x_3 = 5/7\): weight used = 15, value \(= 17 + 11 \cdot 5/7 = 174/7 \approx 24.857\)
The LP optimum is \(z^*_{\mathrm{LP}} = 174/7 \approx 24.857\).
The B&B Tree
Branch and Bound explores a tree of sub-problems. At each node we solve the LP relaxation to obtain an upper bound. We branch on a fractional variable, creating two children by fixing that variable to 0 or 1. We prune a node when its LP bound cannot improve the best integer solution found so far.
The branching variable is chosen as the most fractional variable in the LP solution. Here \(x_3 = 5/7\) is fractional at the root, so we branch on \(x_3\).
Reading the tree:
- Node 0 (root): LP bound = 24.857, branching variable \(x_3 = 5/7\).
- Node 2 (\(x_3 = 1\)): after fixing \(x_3 = 1\) we have 8 units of remaining capacity. The greedy LP fills it with items 5, 2, 1 exactly (weights 2+3+5=10 > 8 — actually items 5 and 2 fit: 2+3=5, then item 1 needs 5 but only 3 remain, so item 1 is fractional). In the full B&B tree this node happens to yield the integer solution \(\{1,2,3\}\) with \(z=24\) directly after a sub-branch. For clarity the tree above collapses that sub-exploration and marks it as the optimal node.
- Nodes 3 and 4: both pruned because their best achievable value (23 and 23.5) cannot exceed the incumbent \(z^* = 24\).
LP Bound vs. ILP Progress
At each node of the B&B tree we have an LP upper bound and a (possibly updated) best integer solution found so far. The chart below shows how the gap closes as we explore the tree.
The key observation: once the integer solution \(z=24\) is found at Node 2, every subsequent node with LP bound \(\leq 24\) is immediately pruned. The gap between the LP bound (24.857) and the ILP optimum (24) is only 0.857, which is why B&B terminates quickly on this instance.
Why LP Relaxations Work
Every feasible integer solution is also feasible for the LP relaxation (we simply relax \(x_j \in \{0,1\}\) to \(0 \leq x_j \leq 1\)). Therefore the LP optimum is always an upper bound on the ILP optimum:
\[ z^*_{\mathrm{ILP}} \;\leq\; z^*_{\mathrm{LP}} \]
The chart below illustrates this for our knapsack: every integer-feasible solution (dots) lies at or below the LP relaxation value (dashed line).
Why this matters for Branch and Bound:
- The LP relaxation always gives a valid upper bound — we can safely discard any sub-problem whose LP bound is no better than the best integer solution in hand.
- The bound gets tighter as we fix more variables (each child node has a smaller LP feasible region than its parent).
- The algorithm is exact: when a leaf node has an integer LP solution, that solution is also optimal for its sub-problem — and if its value equals the LP bound of the root, we have found the global ILP optimum.