Lesson 18: The Branch and Bound Method¶
18.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Explain branching, bounding and fathoming.
- Construct a complete branch-and-bound tree for an integer programme.
- Apply the three fathoming rules.
- Solve 0–1 knapsack problems by branch and bound.
- Choose branching and node-selection strategies, and interpret the optimality gap.
18.2 The Idea¶
Cutting planes (L16–L17) tighten the feasible region. Branch and bound instead partitions it.
Developed by Land and Doig (1960), it is the backbone of every commercial MILP solver.
The three operations¶
BRANCHING. If the LP relaxation gives a fractional \(x_k = \beta\), create two sub-problems:
These are exhaustive and mutually exclusive for integer \(x_k\) — no integer solution is lost, and the fractional value \(\beta\) is excluded from both.
BOUNDING. The LP relaxation of each sub-problem gives an upper bound (for maximisation) on the best integer solution in that branch:
FATHOMING. A node is fathomed (closed, needing no further exploration) when any of three conditions holds.
The three fathoming rules¶
| Rule | Condition | Reason |
|---|---|---|
| 1. Infeasible | the LP relaxation has no solution | nothing lies below this node |
| 2. Integer | the LP solution is already all-integer | it is the best in this branch; update the incumbent if better |
| 3. Bounded | \(Z_{LP}(\text{node}) \le Z_{\text{incumbent}}\) | no solution here can beat what we have |
Definition (Incumbent). The best integer feasible solution found so far. It provides the lower bound \(Z_{\text{incumbent}} \le Z_{IP}^{*}\).
Termination. When every node is fathomed, the incumbent is the optimum.
The optimality gap¶
where the best bound is the largest \(Z_{LP}\) among unfathomed nodes. The gap is a certificate: a 2 % gap proves the incumbent is within 2 % of optimal, even if the search is stopped early.
18.3 The Algorithm¶
1. Solve the LP relaxation at the ROOT.
If integer -> DONE.
2. Set incumbent Z* = -infinity (maximisation)
3. While unfathomed nodes remain:
a. SELECT a node (see strategies below)
b. SOLVE its LP relaxation
c. FATHOM if: infeasible OR integer OR Z_LP <= Z*
-- if integer and better than Z*, UPDATE the incumbent
d. Otherwise BRANCH on a fractional variable -> two child nodes
4. The incumbent is OPTIMAL
Branching-variable strategies¶
| Strategy | Rule | Comment |
|---|---|---|
| Most fractional | pick \(x_k\) with \(f_k\) closest to 0.5 | simple, commonly taught |
| Lowest index | pick the first fractional variable | trivial, poor |
| Pseudo-cost | estimate each variable's historical impact on the bound | best in practice |
| Strong branching | tentatively solve both children before deciding | expensive but very effective |
Node-selection strategies¶
| Strategy | Behaviour | Trade-off |
|---|---|---|
| Depth-first (LIFO) | dive to the bottom | finds an incumbent fast, low memory |
| Best-bound (best-first) | expand the node with the largest \(Z_{LP}\) | fewest nodes overall, high memory |
| Hybrid | dive first for an incumbent, then best-bound | what solvers actually do |
18.4 Worked Example — Complete Tree¶
(The LP relaxation was solved in L03 and L05: optimum \((3, 1.5)\) with \(Z = 21\).)
Node 0 (root)¶
\(x_2\) is fractional ⟹ branch on \(x_2\). Incumbent \(Z^{*} = -\infty\).
Node 1: x₂ ≤ 1¶
Solving the LP with the extra constraint \(x_2\le1\):
\(x_1\) fractional ⟹ branch further. Not fathomed.
Node 2: x₂ ≥ 2¶
ALL INTEGER ⟹ FATHOM by Rule 2.
Node 3: x₂≤1, x₁≤3¶
ALL INTEGER ⟹ FATHOM by Rule 2. And \(19 > 18\):
Node 4: x₂≤1, x₁≥4¶
(Check feasibility: \(6(4)+0 = 24 \le 24\) ✓ binding; \(4+0 = 4\le6\) ✓.)
ALL INTEGER ⟹ FATHOM by Rule 2. And \(20 > 19\):
The tree¶
Node 0: (3, 1.5) Z=21
|
branch on x2 (fractional)
+--------------+---------------+
| |
Node 1: x2 <= 1 Node 2: x2 >= 2
(3.333, 1) Z = 20.667 (2, 2) Z = 18
| INTEGER -> FATHOM
branch on x1 (fractional) incumbent = 18
+------+-------+
| |
Node 3: x1<=3 Node 4: x1>=4
(3, 1) Z=19 (4, 0) Z=20
INTEGER INTEGER
FATHOM FATHOM
incumbent=19 incumbent=20 <-- OPTIMAL
All nodes fathomed.
Verification. \(6(4)+4(0) = 24\le24\) ✓; \(4+2(0) = 4\le6\) ✓; \(Z = 20\) ✓.
The integrality gap. \(Z_{LP} - Z_{IP} = 21 - 20 = 1\) (4.8 %).
A striking observation. The LP optimum was \((3, 1.5)\), and rounding it down gives \((3,1)\) with \(Z = 19\) — but the true optimum is \((4,0)\) with \(Z = 20\).
Nodes explored: 5. Complete enumeration over \(x_1\in\{0..4\}\), \(x_2\in\{0..3\}\) would test 20 combinations. On larger problems the saving is astronomical.
18.5 Solved Problems¶
Problem 1 — Branch and bound with fathoming by bound¶
Solve \(\max\ Z = 8x_1+11x_2+6x_3+4x_4\) subject to \(5x_1+7x_2+4x_3+3x_4\le14\) with all \(x_j\) binary.
Solution.
Step 1 — the LP relaxation (a knapsack). Rank by value-to-weight ratio:
| Item | Value | Weight | Ratio |
|---|---|---|---|
| 2 | 11 | 7 | \(11/7 = 1.571\) |
| 1 | 8 | 5 | \(8/5 = 1.600\) ← best |
| 3 | 6 | 4 | \(6/4 = 1.500\) |
| 4 | 4 | 3 | \(4/3 = 1.333\) |
Fill greedily by ratio: item 1 (weight 5, running 5), item 2 (weight 7, running 12), then item 3 needs 4 but only 2 remain ⟹ take \(\tfrac24 = 0.5\) of it.
\(x_3\) fractional ⟹ branch on \(x_3\).
Node 1: \(x_3 = 0\). Remaining capacity for items 1, 2, 4: greedy gives items 1 and 2 (weight 12), then item 4 needs 3 but 2 remain ⟹ \(\tfrac23\) of item 4.
Node 2: \(x_3 = 1\). Capacity left \(= 14-4 = 10\). Greedy on items 1, 2, 4: item 1 (5, running 5), then item 2 needs 7 but 5 remain ⟹ \(\tfrac57\) of item 2.
Take node 2 first (larger bound — best-first). Branch on \(x_2\).
Node 3: \(x_3=1\), \(x_2=0\). Capacity 10 for items 1, 4: both fit (\(5+3 = 8 \le 10\)).
Node 4: \(x_3=1\), \(x_2=1\). Weight so far \(4+7 = 11\), capacity left 3. Item 1 needs 5 ✗; item 4 needs 3 ✓ — exactly fits.
Back to Node 1 (\(x_3 = 0\), bound 21.667).
Branch on \(x_4\).
Node 5: \(x_3=0\), \(x_4=0\). Items 1, 2 only: weight \(5+7=12\le14\) ✓.
\(19 < 21\) ⟹ fathom, incumbent unchanged.
Node 6: \(x_3=0\), \(x_4=1\). Capacity left \(14-3 = 11\). Greedy: item 1 (5, left 6), item 2 needs 7 ⟹ \(\tfrac67\) of it.
\(21.429 > 21\) ⟹ explore. Branch on \(x_2\).
Node 7: \(x_3=0,x_4=1,x_2=0\). Item 1 fits.
Node 8: \(x_3=0,x_4=1,x_2=1\). Weight \(3+7 = 10\), capacity left 4. Item 1 needs 5 ✗.
All nodes fathomed.
Verification. Weight \(= 7+4+3 = 14 \le 14\) ✓ (exactly full). Value \(= 11+6+4 = 21\) ✓.
The key insight. The greedy ratio rule put item 1 first (ratio 1.60), but the optimum excludes it. Item 1's weight of 5 crowds out the combination \(\{2,3,4\}\) that exactly fills the knapsack.
Nodes explored: 9. Complete enumeration would be \(2^4 = 16\). The saving is modest here but grows exponentially with problem size.
Problem 2 — Fathoming by bound saves an entire subtree¶
Continue a branch-and-bound tree where the incumbent is \(Z^{*} = 47\) and three unexplored nodes have LP bounds 52, 45 and 47. Which can be fathomed?
Solution.
Node with bound 52.
An integer solution worth up to 52 might exist below it.
Node with bound 45.
Every solution in this subtree has \(Z \le 45 < 47\), so none can beat the incumbent. The entire subtree is discarded without a single further LP solve.
Node with bound 47.
This depends on convention.
- If we want any one optimal solution: fathom (nothing strictly better lies below).
- If we want all optimal solutions: explore (an alternate optimum with \(Z = 47\) may lie here).
Standard practice: fathom when \(Z_{LP} \le Z^{*}\), using \(\le\) rather than \(<\). Solvers offer a "find all optima" mode that switches to strict inequality.
Quantifying the saving. Suppose the node with bound 45 would have generated a subtree of 200 nodes. Each node requires an LP solve at, say, 5 ms.
On a problem with thousands of such prunings, this is the difference between seconds and hours.
The current optimality gap.
Reporting. "Best solution found: 47. Proven within 10.6 % of optimal." If the deadline arrives before the gap closes, that statement is still a rigorous, defensible result.
Problem 3 — Branching-variable choice affects tree size¶
An LP relaxation gives \(x_1 = 2.9\), \(x_2 = 4.5\), \(x_3 = 7.1\). Which variable should be branched on under each strategy, and why does it matter?
Solution.
Fractional parts.
Most-fractional rule (closest to 0.5):
Lowest-index rule: branch on \(x_1\) (the first fractional variable).
Why "most fractional" is preferred. Consider the two extremes.
Branching on \(x_3 = 7.1\):
- \(x_3 \le 7\) — the LP optimum is only 0.1 away, so this child's bound barely drops. Weak.
- \(x_3\ge8\) — a jump of 0.9, cutting off a lot. Strong.
The tree is unbalanced: one child does almost no work, so progress is slow.
Branching on \(x_2 = 4.5\):
- \(x_2\le4\) — moves 0.5 away.
- \(x_2\ge5\) — moves 0.5 away.
Both children tighten equally, so the tree is balanced and the bound drops on both sides.
A concrete estimate. If balanced branching reduces the bound by \(\delta\) on both sides while unbalanced reduces it by \(0.1\delta\) and \(0.9\delta\), the number of levels needed to close a gap \(G\) is roughly \(\log_2\)-like for the former and much larger for the latter.
Why pseudo-cost branching beats both. Most-fractional is a heuristic proxy for what we actually want: the variable whose branching most raises the lower bound. Pseudo-cost branching records, for each variable, how much the objective actually degraded in past branchings, and picks the variable with the best historical record. Modern solvers combine it with strong branching (a tentative one-step lookahead) at the top of the tree, where decisions matter most.
Empirical impact. On standard MIPLIB benchmarks, switching from most-fractional to pseudo-cost branching typically reduces node counts by an order of magnitude.
Problem 4 — A 0–1 knapsack with a strong bound¶
Solve by branch and bound: maximise \(Z = 40x_1+30x_2+50x_3+10x_4\) subject to \(3x_1+2x_2+5x_3+x_4 \le 7\), \(x_j\in\{0,1\}\).
Solution.
Ratios.
| Item | Value | Weight | Ratio |
|---|---|---|---|
| 2 | 30 | 2 | 15.0 |
| 1 | 40 | 3 | 13.3 |
| 4 | 10 | 1 | 10.0 |
| 3 | 50 | 5 | 10.0 |
Root LP. Fill by ratio: item 2 (w 2, running 2), item 1 (w 3, running 5), then item 4 (w 1, running 6), then item 3 needs 5 but 1 remains ⟹ \(\tfrac15\) of item 3.
Branch on \(x_3\).
Node 1: \(x_3 = 0\). Items 1, 2, 4 all fit: \(3+2+1 = 6\le7\) ✓.
Node 2: \(x_3 = 1\). Weight used 5, capacity left 2. Greedy on items 1, 2, 4 by ratio: item 2 (w 2) exactly fits.
\(80 = 80\) ⟹ fathom (an alternate optimum, not an improvement).
All nodes fathomed after only 3 LP solves.
Verification.
Confirm by complete enumeration (\(2^4 = 16\) subsets — the feasible ones with the largest value):
| Subset | Weight | Value |
|---|---|---|
| \(\{1,2,4\}\) | 6 | 80 |
| \(\{2,3\}\) | 7 | 80 |
| \(\{1,2\}\) | 5 | 70 |
| \(\{3,4\}\) | 6 | 60 |
| \(\{1,3\}\) | 8 | ✗ infeasible |
Why only 3 nodes sufficed. The root bound of 90 was close to the true optimum of 80, and both children happened to be integral immediately. A tight relaxation is the single best predictor of a small tree.
Alternate optima again. Two different item sets give 80. Report both — the decision-maker may prefer one on grounds outside the model (perishability, supplier relationships, storage).
Problem 5 — A complete production-planning MILP¶
A factory can run up to 3 machine types. Machine A costs ₹20 lakh and produces 100 units/month; machine B costs ₹35 lakh, 180 units; machine C costs ₹15 lakh, 70 units. Budget ₹60 lakh. Demand is 250 units/month, and unmet demand costs ₹0.3 lakh per unit in lost margin. How many of each machine should be bought?
Solution.
Decision variables.
Objective (minimise total cost, ₹ lakh):
Constraints.
Budget:
Demand (production plus shortfall must meet demand):
This is a MILP — integer machine counts, continuous shortfall.
Solution by enumerating budget-feasible machine combinations.
| \((n_A,n_B,n_C)\) | Capital | Output | Shortfall \(u\) | Shortfall cost | Total \(Z\) |
|---|---|---|---|---|---|
| \((0,0,0)\) | 0 | 0 | 250 | 75.0 | 75.0 |
| \((0,0,4)\) | 60 | 280 | 0 | 0 | 60.0 |
| \((1,0,2)\) | 50 | 240 | 10 | 3.0 | 53.0 |
| \((0,1,1)\) | 50 | 250 | 0 | 0 | 50.0 ← |
| \((1,1,0)\) | 55 | 280 | 0 | 0 | 55.0 |
| \((2,0,1)\) | 55 | 270 | 0 | 0 | 55.0 |
| \((3,0,0)\) | 60 | 300 | 0 | 0 | 60.0 |
| \((0,0,3)\) | 45 | 210 | 40 | 12.0 | 57.0 |
| \((1,0,1)\) | 35 | 170 | 80 | 24.0 | 59.0 |
| \((0,1,0)\) | 35 | 180 | 70 | 21.0 | 56.0 |
| \((2,0,0)\) | 40 | 200 | 50 | 15.0 | 55.0 |
Verification.
The LP relaxation, for comparison. Allowing fractional machines, the cheapest capacity per unit is machine B: \(35/180 = ₹0.194\) lakh per unit. To produce 250 units:
A small gap — because the demand happens to be met almost exactly by an integer combination.
Advice to management.
-
Buy 1 × B and 1 × C for ₹50 lakh. Demand is exactly met with no shortfall cost.
-
₹10 lakh of budget remains unspent. The model says this is correct — adding another machine C (₹15 lakh) exceeds the budget, and there is no unmet demand to justify it anyway.
-
The capacity is exactly 250 with zero margin. This is a fragile plan: any breakdown causes immediate shortfall. Recommend re-running with a reliability constraint (e.g. capacity \(\ge 275\) to allow 10 % downtime), which would push toward \((1,1,0)\) at ₹55 lakh for 280 units — ₹5 lakh more for a 12 % safety margin.
-
Sensitivity on the shortfall cost. At ₹0.3 lakh per unit, meeting demand fully is worth it. If the shortfall cost fell below
\[ \frac{50 - 35}{70} = ₹0.214\ \text{lakh/unit} \]then buying only machine B (₹35 lakh, 70 units short) would become cheaper. Verify the ₹0.3 figure carefully — the recommendation flips below ₹0.214.
18.6 Practice Problems¶
- LP relaxation gives \(x = 3.7\). State both branch constraints. [Ans: \(x\le3\) and \(x\ge4\)]
- Incumbent 25; node bound 24. Fathom? [Ans: yes, Rule 3]
- Incumbent 25; node bound 30 and all-integer LP solution. Fathom? [Ans: yes, Rule 2; update incumbent to 30]
- Given fractional values 1.2, 5.5, 8.9, which does most-fractional branching choose? [Ans: 5.5]
- Compute the gap if the incumbent is 120 and the best bound is 132. [Ans: 10 %]
- Solve by branch and bound: \(\max 3x_1+5x_2\) s.t. \(2x_1+4x_2\le11\), integer.
- Explain why depth-first search is used to find an early incumbent.
18.7 Summary¶
- Branch and bound partitions the feasible region rather than tightening it: branch on a fractional \(x_k\) into \(x_k\le\lfloor\beta\rfloor\) and \(x_k\ge\lceil\beta\rceil\) — exhaustive and mutually exclusive for integers.
- The LP relaxation at each node gives an upper bound; the best integer solution found is the incumbent (a lower bound).
- Three fathoming rules: infeasible, all-integer, or bound \(\le\) incumbent. Rule 3 prunes whole subtrees and is where the efficiency comes from.
- The optimality gap \(\frac{\text{best bound}-\text{incumbent}}{\text{incumbent}}\) certifies how close the incumbent is — turning an incomplete search into a rigorous approximation.
- Branching strategy: most-fractional beats lowest-index (balanced trees); pseudo-cost and strong branching beat both in practice, often by an order of magnitude in node count.
- Node selection: depth-first finds an incumbent fast (good pruning, low memory); best-bound minimises node count; solvers use a hybrid.
- The integer optimum can be at a completely different vertex from the LP optimum — the worked example's rounding gave 19 against a true optimum of 20 at \((4,0)\).
- Modern solvers combine this with cuts (L16–L17) as branch and cut.
Next lesson: L19 — Network scheduling: the Critical Path Method (CPM).
Practise now: unit2-games-networks-lab.html → Branch & Bound Lab: watch the tree grow node by
node, with bounds, incumbents and fathoming reasons annotated.