Skip to content

Lesson 18: The Branch and Bound Method

18.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Explain branching, bounding and fathoming.
  2. Construct a complete branch-and-bound tree for an integer programme.
  3. Apply the three fathoming rules.
  4. Solve 0–1 knapsack problems by branch and bound.
  5. 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.

\[ \boxed{\ \textbf{Divide and conquer: split the problem, bound each piece, discard pieces that cannot contain the optimum.}\ } \]

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:

\[ \text{Left: } x_k \le \lfloor\beta\rfloor \qquad\qquad \text{Right: } x_k \ge \lceil\beta\rceil \]

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:

\[ Z_{IP}(\text{branch}) \ \le\ Z_{LP}(\text{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
\[ \boxed{\ \textbf{Rule 3 is where the power lies — it prunes entire subtrees without exploring them.}\ } \]

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

\[ \boxed{\ \text{gap} \ =\ \frac{Z_{\text{best bound}} - Z_{\text{incumbent}}}{Z_{\text{incumbent}}}\times100\%\ } \]

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
\[ \boxed{\ \textbf{Depth-first finds a good incumbent early, which then prunes aggressively by Rule 3.}\ } \]

18.4 Worked Example — Complete Tree

\[ \begin{aligned} \max\ & Z = 5x_1 + 4x_2\\ \text{s.t. } & 6x_1 + 4x_2 \le 24\\ & x_1 + 2x_2 \le 6\\ & x_1, x_2 \ge 0 \ \text{and INTEGER} \end{aligned} \]

(The LP relaxation was solved in L03 and L05: optimum \((3, 1.5)\) with \(Z = 21\).)

Node 0 (root)

\[ x_1 = 3, \quad x_2 = 1.5, \quad Z_{LP} = 21 \]

\(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 = \tfrac{10}{3} = 3.333, \quad x_2 = 1, \quad Z_{LP} = 5(3.333)+4 = \mathbf{20.667} \]

\(x_1\) fractional ⟹ branch further. Not fathomed.

Node 2: x₂ ≥ 2

\[ x_1 = 2, \quad x_2 = 2, \quad Z_{LP} = 10 + 8 = \mathbf{18} \]

ALL INTEGER ⟹ FATHOM by Rule 2.

\[ \boxed{\ \text{Incumbent updated: } Z^{*} = 18 \ \text{at } (2,2)\ } \]

Node 3: x₂≤1, x₁≤3

\[ x_1 = 3, \quad x_2 = 1, \quad Z_{LP} = 15 + 4 = \mathbf{19} \]

ALL INTEGER ⟹ FATHOM by Rule 2. And \(19 > 18\):

\[ \boxed{\ \text{Incumbent updated: } Z^{*} = 19 \ \text{at } (3,1)\ } \]

Node 4: x₂≤1, x₁≥4

\[ x_1 = 4, \quad x_2 = 0, \quad Z_{LP} = 20 + 0 = \mathbf{20} \]

(Check feasibility: \(6(4)+0 = 24 \le 24\) ✓ binding; \(4+0 = 4\le6\) ✓.)

ALL INTEGER ⟹ FATHOM by Rule 2. And \(20 > 19\):

\[ \boxed{\ \text{Incumbent updated: } Z^{*} = 20 \ \text{at } (4,0)\ } \]

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.

\[ \boxed{\ x_1^{*} = 4, \quad x_2^{*} = 0, \quad Z^{*}_{IP} = 20\ } \]

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\).

\[ \boxed{\ \textbf{Rounding gave 19; branch and bound found 20. A different vertex entirely.}\ } \]

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.

\[ \vec x = (1,\ 1,\ 0.5,\ 0), \qquad Z_{LP} = 8 + 11 + 3 = \mathbf{22} \]

\(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.

\[ \vec x = (1,1,0,0.667), \qquad Z_{LP} = 8+11+2.667 = \mathbf{21.667} \]

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.

\[ \vec x = (1,\ 0.714,\ 1,\ 0), \qquad Z_{LP} = 8 + 7.857 + 6 = \mathbf{21.857} \]

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\)).

\[ \vec x = (1,0,1,1), \qquad Z = 8+6+4 = \mathbf{18} \quad \textbf{ALL INTEGER} \]
\[ \boxed{\ \text{Incumbent } Z^{*} = 18\ } \]

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.

\[ \vec x = (0,1,1,1), \qquad Z = 11+6+4 = \mathbf{21} \quad \textbf{ALL INTEGER} \]
\[ \boxed{\ \text{Incumbent updated: } Z^{*} = 21 \ \text{at } (0,1,1,1)\ } \]

Back to Node 1 (\(x_3 = 0\), bound 21.667).

\[ 21.667 > 21 \ \Longrightarrow\ \textbf{cannot fathom by bound — must explore.} \]

Branch on \(x_4\).

Node 5: \(x_3=0\), \(x_4=0\). Items 1, 2 only: weight \(5+7=12\le14\) ✓.

\[ \vec x = (1,1,0,0), \qquad Z = 19 \quad \textbf{INTEGER} \]

\(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.

\[ Z_{LP} = 4 + 8 + \tfrac67(11) = 4+8+9.429 = \mathbf{21.429} \]

\(21.429 > 21\) ⟹ explore. Branch on \(x_2\).

Node 7: \(x_3=0,x_4=1,x_2=0\). Item 1 fits.

\[ \vec x = (1,0,0,1), \quad Z = 12 \quad \textbf{INTEGER}, \ 12<21 \Rightarrow \textbf{fathom} \]

Node 8: \(x_3=0,x_4=1,x_2=1\). Weight \(3+7 = 10\), capacity left 4. Item 1 needs 5 ✗.

\[ \vec x = (0,1,0,1), \quad Z = 15 \quad \textbf{INTEGER}, \ 15<21 \Rightarrow \textbf{fathom} \]

All nodes fathomed.

\[ \boxed{\ \vec x^{*} = (0,\ 1,\ 1,\ 1), \qquad Z^{*} = 21\ } \]

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.

\[ \boxed{\ \textbf{Greedy gives 19 (items 1,2); branch and bound gives 21. Ratios guide, they do not decide.}\ } \]

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.

\[ 52 > 47 \ \Longrightarrow\ \textbf{CANNOT fathom — must explore.} \]

An integer solution worth up to 52 might exist below it.

Node with bound 45.

\[ 45 < 47 = Z^{*} \ \Longrightarrow\ \textbf{FATHOM by Rule 3.} \]

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.

\[ 47 = Z^{*} \]

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.

\[ \text{Saving} = 200 \times 5\ \text{ms} = \mathbf{1\ \text{second}} \]

On a problem with thousands of such prunings, this is the difference between seconds and hours.

The current optimality gap.

\[ \text{best bound among unfathomed nodes} = 52 \]
\[ \text{gap} = \frac{52-47}{47}\times100\% = \mathbf{10.6\%} \]

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.

\[ \boxed{\ \textbf{The gap turns an incomplete search into a certified approximation.}\ } \]

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.

\[ f_1 = 0.9, \qquad f_2 = 0.5, \qquad f_3 = 0.1 \]

Most-fractional rule (closest to 0.5):

\[ |f_1 - 0.5| = 0.4, \qquad |f_2-0.5| = \mathbf{0}, \qquad |f_3-0.5| = 0.4 \]
\[ \boxed{\ \textbf{Branch on } x_2\ } \]

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.

\[ \boxed{\ \textbf{Balanced branching halves the problem; unbalanced branching shaves it.}\ } \]

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.

\[ \vec x = (1,1,0.2,1), \qquad Z_{LP} = 40+30+10+10 = \mathbf{90} \]

Branch on \(x_3\).

Node 1: \(x_3 = 0\). Items 1, 2, 4 all fit: \(3+2+1 = 6\le7\) ✓.

\[ \vec x = (1,1,0,1), \qquad Z = 40+30+10 = \mathbf{80} \quad \textbf{ALL INTEGER} \]
\[ \boxed{\ \text{Incumbent } Z^{*} = 80\ } \]

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.

\[ \vec x = (0,1,1,0), \qquad Z = 30+50 = \mathbf{80} \quad \textbf{ALL INTEGER} \]

\(80 = 80\) ⟹ fathom (an alternate optimum, not an improvement).

All nodes fathomed after only 3 LP solves.

\[ \boxed{\ Z^{*} = 80, \ \text{achieved at BOTH } (1,1,0,1) \text{ and } (0,1,1,0)\ } \]

Verification.

\[ (1,1,0,1): \ 3+2+1 = 6\le7 \ \checkmark, \quad Z = 80 \]
\[ (0,1,1,0): \ 2+5 = 7\le7 \ \checkmark \ \text{(exactly full)}, \quad Z = 80 \]

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
\[ \textbf{Maximum} = 80 \ \checkmark \]

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.

\[ n_A, n_B, n_C \ \ge 0 \ \text{and INTEGER} \qquad \text{(number of each machine)} \]
\[ u \ \ge 0 \ \text{CONTINUOUS} \qquad \text{(units of unmet demand)} \]

Objective (minimise total cost, ₹ lakh):

\[ \min\ Z = 20n_A + 35n_B + 15n_C + 0.3u \]

Constraints.

Budget:

\[ 20n_A + 35n_B + 15n_C \ \le\ 60 \]

Demand (production plus shortfall must meet demand):

\[ 100n_A + 180n_B + 70n_C + u \ \ge\ 250 \]

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
\[ \boxed{\ \textbf{Buy 1 machine B and 1 machine C. Capital ₹50 lakh, demand fully met, } Z^{*} = ₹50\ \text{lakh.}\ } \]

Verification.

\[ \text{Budget: } 35+15 = 50 \le 60 \ \checkmark \ \text{(₹10 lakh unspent)} \]
\[ \text{Output: } 180+70 = 250 \ge 250 \ \checkmark \ \text{(exactly meets demand, } u = 0) \]

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:

\[ n_B = \frac{250}{180} = 1.389, \qquad Z_{LP} = 35(1.389) = ₹48.6\ \text{lakh} \]
\[ \text{Integrality gap} = 50 - 48.6 = \mathbf{₹1.4\ \text{lakh}} \ (2.9\%) \]

A small gap — because the demand happens to be met almost exactly by an integer combination.

Advice to management.

  1. Buy 1 × B and 1 × C for ₹50 lakh. Demand is exactly met with no shortfall cost.

  2. ₹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.

  3. 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.

  4. 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.

\[ \boxed{\ \textbf{Always report the parameter value at which the recommendation changes.}\ } \]

18.6 Practice Problems

  1. LP relaxation gives \(x = 3.7\). State both branch constraints. [Ans: \(x\le3\) and \(x\ge4\)]
  2. Incumbent 25; node bound 24. Fathom? [Ans: yes, Rule 3]
  3. Incumbent 25; node bound 30 and all-integer LP solution. Fathom? [Ans: yes, Rule 2; update incumbent to 30]
  4. Given fractional values 1.2, 5.5, 8.9, which does most-fractional branching choose? [Ans: 5.5]
  5. Compute the gap if the incumbent is 120 and the best bound is 132. [Ans: 10 %]
  6. Solve by branch and bound: \(\max 3x_1+5x_2\) s.t. \(2x_1+4x_2\le11\), integer.
  7. 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.