Worked examples — Branch and bound

This page is the drill hall for Branch and Bound. The parent note taught what pruning is and why bounds must be optimistic. Here we hit every kind of situation B&B can throw at you — maximization, minimization, ties, zero-capacity edge cases, "nothing prunes" worst cases, a word problem, and an exam twist.

Before we start, a one-line reminder of the two golden rules (built fully in the parent):

Recall The prune rule in both directions

For maximization (e.g. 0-1 Knapsack): the bound is an upper bound (best possible value). Prune a node when $\text{UB}\le \text{incumbent}$. For minimization (e.g. Travelling Salesman Problem): the bound is a lower bound (least possible cost). Prune a node when $\text{LB}\ge \text{incumbent}$. incumbent = value/cost of the best complete solution found so far.

---

The scenario matrix

Think of every B&B problem as a point in this grid. To not be surprised by an exam, you must have seen each row at least once.

Cell	What makes it distinct	Covered by
A. Max problem, pruning happens	upper bound, incumbent beats a subtree	Example 1
B. Min problem, pruning happens	lower bound, forced/forbidden edges	Example 2
C. Zero / degenerate input	capacity $=0$, empty item set, single city	Example 3
D. Tie in bounds	two nodes share the same bound — tie-break rule	Example 4
E. Worst case, nothing prunes	bound never beats incumbent early → full tree	Example 5
F. Item bigger than capacity	an item can never fit; must be forced out	Example 6
G. Real-world word problem	translate English → objective + constraints	Example 7
H. Exam twist: wrong-direction bound	spot why a "clever" bound is invalid	Example 8

Each example is tagged with its cell. Together they fill the whole grid.

---

Example 1 — Cell A: maximization with real pruning

Step 1 — Root bound (the optimistic estimate). Fill fractionally in density order: A full $(+40,w=2)$, B full $(+30,w=7)$, then C wants weight 10 but only $10-7=3$ is left, so take fraction $\frac{3}{10}\cdot 50=15$. ${\text{bound}}_{\text{root}}=40+30+15=85.$ Why this step? The fractional fill (from the greedy relaxation) is a valid upper bound — allowing fractions only ever helps, so no integer solution can beat 85.

Step 2 — Branch on A (highest density first). Recall $p$ = decided profit, $w$ = decided weight (defined at the top of the page).

• Include A $(p=40,w=2)$: bound $=40+30(\text{B})+\frac{3}{10}\cdot 50=85$.
• Exclude A $(p=0,w=0)$: B full $(+30,w=5)$, then C fraction $\frac{5}{10}\cdot 50=25$: bound $=55$.

Why this step? We split into two smaller subproblems ("A is in" / "A is out"). Least-Cost B&B will chase the higher bound first (85).

Step 3 — Expand include-A, then include-B. $(p=70,w=7)$. Remaining capacity $3$. C is next but weight 10 doesn't fit as a whole → its integer completion adds nothing. So the complete feasible solution {A,B} has value $70$. Set incumbent $=70$. Why this step? A complete feasible solution is the first real number B&B can trust — until now every "bound" was only an optimistic guess. Recording it as the incumbent gives us the yardstick ("beat 70 or die") that all future pruning is measured against; without a stored incumbent there is nothing to compare bounds to.

Step 4 — Prune. The exclude-A node has bound $55$. Since $55\le 70$, prune it — the entire exclude-A subtree vanishes in one comparison. Also check {A,C}: weight $2+10=12>10$, infeasible. {A,B,D}: weight $2+5+5=12>10$, infeasible.

Verify: Brute-force the feasible sets under $W=10$: {A}=40, {A,B}=70 (w7), {A,D}=50 (w7), {B}=30, {B,D}=40 (w10), {C}=50, {D}=10. Max $=70=A,B$. ✔ Matches, and yes the exclude-A branch was pruned.

---

Example 2 — Cell B: minimization, forcing an edge raises the bound

Step 1 — Root lower bound (2-min rule). Each city touches exactly 2 tour edges, so it contributes at least its two cheapest incident edges. Sum, then halve (each edge counted by both endpoints).

• City 1: cheapest two of $\{1,4,3\}=1+3=4$
• City 2: cheapest two of $\{1,2,5\}=1+2=3$
• City 3: cheapest two of $\{4,2,6\}=2+4=6$
• City 4: cheapest two of $\{3,5,6\}=3+5=8$

${\text{LB}}_{\text{root}}=\frac{1}{2}(4+3+6+8)=\frac{21}{2}=\mathrm{10.5.}$

Why this step? This is an under-estimate of any real tour, so it's a safe lower bound for a min problem — the mirror image of the knapsack upper bound.

Step 2 — Force edge $1-2$ into the tour. Now city 1 must use edge $(1,2)=1$ as one of its two edges. Its cheapest allowed pair becomes $1+3=4$ (still $1$ and $3$ here). City 2 must use $(1,2)=1$ too; cheapest pair $1+2=3$. Cities 3, 4 unchanged. ${\text{LB}}_{\text{force}}=\frac{1}{2}(4+3+6+8)=\mathrm{10.5.}$ Why this step? Fixing an edge in a branch changes the constraints each endpoint city must satisfy, so its "two cheapest allowed edges" may change — we must recompute the bound to keep it valid for this restricted subproblem. Here it stayed equal only because $(1,2)$ was already each endpoint's cheapest edge, so no city was forced to give up a cheaper option.

Step 3 — Force a worse edge to see the rise. Force $1-3$ ($=4$) instead. City 1 must use $4$; cheapest allowed pair $=4+1=5$ (must include the forced 4, plus next cheapest 1). City 3 must use $4$; cheapest allowed pair $=4+2=6$. ${\text{LB}}_{\text{force }1\text{-}3}=\frac{1}{2}(\underset{c1}{\underbrace{5}}+\underset{c2}{\underbrace{3}}+\underset{c3}{\underbrace{6}}+\underset{c4}{\underbrace{8}})=\frac{22}{2}=11.$ The bound rose from $10.5$ to $11$: forcing a non-cheapest edge removes freedom, so the optimistic estimate can only go up.

Verify: The three distinct tours of 4 cities (fix start at 1):

• $1-2-3-4-1=1+2+6+3=12$
• $1-2-4-3-1=1+5+6+4=16$
• $1-3-2-4-1=4+2+5+3=14$

Optimal $=12$. Both bounds ($10.5$, $11$) are $\le 12$ ✔ (valid under-estimates). ✔

---

Example 3 — Cell C: degenerate input (zero capacity)

Step 1 — Root bound. Remaining capacity is $c=W-w=0-0=0$, so nothing fits, not even a fraction: $\text{bound}=0$. Why this step? The fractional fill loop has zero capacity to give away, so it adds nothing.

Step 2 — The only complete solution. The empty set $\{\}$ with value $0$ is feasible. incumbent $=0$.

Step 3 — Prune everything. Every child bound is $0\le \text{incumbent}=0$ → all pruned. No branching happens.

Verify: Max value with $W=0$ is $0$ (empty set is the only feasible set). ✔ Degenerate case handled: answer $0$, tree = just the root.

---

Example 4 — Cell D: two nodes tie on the bound

Step 1 — State the tie. The live set (a priority queue that always hands back the node with the best bound) holds two nodes with the same key $85$. The queue's ordering only ranks by bound; when bounds are equal it does not, by itself, say which to take — so an implementation must supply a tie-break rule as an extra ordering criterion. Why this step? We must first notice that the priority queue is under-specified at a tie, because that is the exact gap where two correct-but-different implementations diverge — pinning down the gap is what lets us reason about whether it can affect the answer.

Step 2 — Choose a tie-break, and say why. A common, practical choice is deeper node first (the node with more decisions already fixed). Why this rule and not another? A deeper node is closer to a complete solution, so expanding it tends to produce an incumbent sooner; an earlier incumbent means earlier pruning of the other tied node's siblings, i.e. less total work. This is a heuristic for speed only — it is not mandated by B&B. Other valid choices (insertion order / "oldest first", or lowest node-id) are equally correct; they just may explore more nodes.

Step 3 — Show correctness is order-independent. Whatever tie-break we use, B&B only ever prunes provably-hopeless nodes ($\text{UB}\le \text{incumbent}$). It never discards a node that could hold a strictly better solution. So the returned optimal value is identical for any tie-break — only the amount of work changes.

Verify: From Example 1 the optimum is $70$ regardless of expansion order. A tie changes speed, not the answer $70$. ✔

---

Example 5 — Cell E: the worst case, nothing prunes

Step 1 — Compute the bounds numerically at each level. All items have density $\frac{10}{10}=1$, and total weight $30\le 100$, so the fractional fill always takes everything remaining. (Recall $p,w,c$ from the top: profit, weight, remaining capacity.)

• Root $(p=0,w=0,c=100)$: fill A,B,C fully $=10+10+10$. $\text{bound}=30$.
• Include-A $(p=10,w=10,c=90)$: add B,C fully $=10+10$. $\text{bound}=10+20=30$.
• Exclude-A $(p=0,w=0,c=100)$: the remaining items are just B,C, whose fractional fill is $10+10=20$, so $\text{bound}=0+20=20$.
• Include-A-Include-B $(p=20,w=20,c=80)$: add C fully $=10$. $\text{bound}=30$.
• Include-A-Exclude-B $(p=10,w=10,c=90)$: add C fully $=10$. $\text{bound}=20$.

The first complete leaf gives incumbent $30$.

Step 2 — Why the equal-value case blocks all pruning (reconciling the prune rule). The golden rule prunes a max-node when $\text{UB}\le \text{incumbent}$ — ties do prune. So why isn't everything cut here? Because B&B records the incumbent as the best complete solution found so far, and updates it only on a strict improvement. Watch the order carefully:

• The very first complete leaf B&B reaches has value $30$; at that moment incumbent was $0$, so it becomes $30$.
• Every other full branch here also completes with value exactly $30$. When B&B is about to record one of them, $30$ is not a strict improvement over incumbent $30$, so the incumbent (and hence the returned solution) doesn't change — but B&B still had to walk down that branch to discover the leaf value $30$ before it could compare.

The subtlety: pruning by $\text{UB}\le \text{incumbent}$ happens at an interior node before expanding it. But here every interior node's bound is $30$ or $20$, and the incumbent only becomes $30$ after the first full leaf. Interior nodes with bound $30$ satisfy $30\le 30$ and would be pruned — once the incumbent is $30$. The trap is that reaching that first $30$-valued leaf already forces B&B to descend one full root-to-leaf spine, and along the way it enters interior nodes whose bound $30$ is not yet dominated (incumbent still $0$). So the first spine is fully explored no matter what, and equal-density flatness means every leaf value merely ties — never strictly beating $30$ to sharpen the incumbent further.

Net effect: essentially the whole tree gets touched. In the strict worst case (bounds never exceed any not-yet-found leaf value early), B&B examines all $2^n$ leaves.

Step 3 — Count leaves and state the optimum. With $n=3$ independent binary choices, the tree has $2^3=8$ leaves, and the optimum (all three fit) is $10+10+10=30$. Why this happens? Flat, equal-density instances give no gap between the optimistic bound and real completions, so early strict domination never occurs. This is exactly the worst case the parent warned about: B&B stays $O(2^n)$ (see Big-O Notation).

Verify: $2^3=8$ subsets; optimum value with $W=100$ is $10+10+10=30$. ✔ Worst-case leaf count $=8=2^n$. ✔

---

Example 6 — Cell F: an item bigger than the whole knapsack

Step 1 — Handle B in the bound. When computing the fractional root bound, B can be partially taken (fractions allowed in the relaxation). Order A,B,C: A full $(+60,w=3)$, B: capacity left $c=6-3=3$, take fraction $\frac{3}{7}\cdot 100\approx 42.857$. Bound $\approx 102.857$. Why this step? The relaxation ignores the integrality constraint, so a too-heavy item may still contribute fractionally to the (optimistic) bound — that's fine, it only over-estimates.

Step 2 — But never branch into including B fully. The "include B" child sets $w=7>6$ → infeasible. We give it bound $-\infty$ — recall from the definition at the top of the page that $-\infty$ just means "the worst possible score for a maximization node," so it is instantly $\le$ any incumbent and pruned (equivalently, we simply never create the node). Only "exclude B" survives. Why this step? Feasibility (from Backtracking) kills the include-B node before any cost bound is even needed.

Step 3 — Finish. Feasible sets under $W=6$: {A}=60(w3), {C}=20(w2), {A,C}=80(w5), {B} infeasible, {}=0. Best $=\{A,C\}=80$.

Verify: Brute force $W=6$: {A}=60, {C}=20, {A,C}=80 (w5≤6), any set with B has w≥7>6 → infeasible. Max $=80$. ✔ The bound $102.857$ over-estimates (valid), and B is only used fractionally. ✔

---

Example 7 — Cell G: real-world word problem

Step 1 — Translate to knapsack. Objective: maximise total profit; constraint: total weight $\le 5$. Densities ₹/kg: P1$=24$, P2$=15$, P3$=6$, P4$=10$ → order P1, P2, P4, P3. Why this step? B&B needs an optimization frame — an objective to maximise and a hard constraint. Naming "profit" as the objective and "$\le 5$ kg" as the constraint turns the English into the exact 0-1 Knapsack shape we already know how to bound.

Step 2 — Root bound. P1 full $(+24,w=1)$, P2 full $(+30,w=3)$, P4: capacity left $c=5-3=2$, weight 4, take fraction $\frac{2}{4}\cdot 40=20$. Bound $=24+30+20=74$.

Step 3 — Branch & prune. Include P1, include P2 $(p=54,w=3)$. Remaining $2$: P4 (w4) doesn't fit whole; P3 (w3) doesn't fit. Complete $\{P1,P2\}=54$ → incumbent $54$. Try include P1, exclude P2, include P4 $(p=64,w=5)$: complete $\{P1,P4\}=64>54$ → incumbent $64$. Now any node with bound $\le 64$ prunes. The naive "grab P4 first" ($\{P4\}=40$) or "highest per-kg only" $\{P1,P2\}=54$ are both beaten.

Step 4 — Confirm optimum. $\{P1,P4\}$: weight $1+4=5\le 5$, profit $24+40=64$.

Verify (units check): weight $1\text{ kg}+4\text{ kg}=5\text{ kg}\le 5\text{ kg}$ ✔; profit in ₹. Brute force all feasible sets ($W=5$): best is $\{P1,P4\}=₹64$. ✔ Greedy-by-density alone would have stopped at $\{P1,P2\}=54$ — B&B beats it.

---

Example 8 — Cell H: exam twist, spot the invalid bound

Step 1 — Recall the requirement. For maximization, the bound must be a guaranteed upper bound: $\text{bound}\ge$ every integer completion of the node. (Parent: "the bound must be a valid over-estimate.") Why this step? The whole proof of correctness rests on "even the best case here can't beat what I have." That proof is only valid if the bound truly is $\ge$ every completion — so we must state that requirement before testing any candidate bound against it.

Step 2 — Test it on Example 1. The true best completion of the root is the real optimum $70$. A correct upper bound must be $\ge 70$. The honest fractional bound is $85$; scaling gives $85\times 0.9=76.5$ — still $\ge 70$ here, but that safety is accidental, not guaranteed.

Step 3 — Break it deliberately. Take a node whose honest fractional bound equals its integer optimum (a "tight" node — e.g. every item fits with no leftover, as in Example 5 where the honest bound $30$ equals the optimum $30$). Then honest bound $=$ optimum $=V$. The scaled bound is $0.9V<V$. If the incumbent equals $V$ (found first in a tied branch), the rule prunes this node because $0.9V\le V$ — discarding the branch that actually contains the true optimum.

Step 4 — Verdict. ${\text{bound}}_{\text{bad}}$ is invalid: scaling an upper bound down can push it below a real completion, so "even the best case is bad" is no longer a proof — it can lie. The lesson: aggressive pruning is allowed only with a provably optimistic bound. A tighter bound must come from a tighter relaxation, never from arbitrarily shrinking a valid one.

Verify: With $V=30$ (Example 5, all fit), honest bound $=30=$ optimum; scaled bound $=0.9\times 30=27<30$. A branch holding the optimum $30$ is pruned when incumbent $=30$ arrives from a tied branch → optimum lost. So the rule is unsafe. ✔ (This mirrors the parent's first "common mistake.")

---

Recall Self-test

For a max problem, prune when? ::: $\text{upper bound}\le \text{incumbent}$ For a min problem, prune when? ::: $\text{lower bound}\ge \text{incumbent}$ Does a tie in bounds change the returned optimum? ::: No — only the work done. When does B&B stay $O(2^n)$? ::: When bounds never strictly beat the incumbent early (flat / equal-density instances). Can an item heavier than $W$ still affect the bound? ::: Yes, fractionally in the relaxation — but its "include" node is infeasible ($-\infty$ bound). Why can't you scale an upper bound down to prune more? ::: It may drop below a real completion and discard the true optimum.

See also: Dynamic Programming (exact but table-based, no pruning), A* Search (B&B's cousin: bound = $g+h$ with an admissible heuristic = optimistic), Hinglish version.