Branch and bound: Exercises — Coding deep dive

Ten graded problems, from "can you spot the vocabulary" up to "design a bound yourself." Every one has a full worked solution hidden inside a collapsible callout — try first, then reveal. Prerequisites live in Branch and bound, with side-trips to Backtracking, Greedy Algorithms, 0-1 Knapsack, and Travelling Salesman Problem.

Level 1 — Recognition

Goal: can you read the vocabulary without tripping.

L1.1 In a minimization B&B, you have an incumbent (best complete solution so far) with cost $47$ . A live node has lower bound $52$ . Do you keep it or prune it?

Recall Solution L1.1

The lower bound is the most optimistic (cheapest) any completion of that node could be. Here even the best case, $52$ , is worse than the $47$ we already own. So we prune. Rule ::: For minimization, prune when $lower_bound \geq incumbent$ . Since $52 \geq 47$ , prune.

L1.2 In a maximization B&B (like 0-1 Knapsack), incumbent value $= 70$ . A node has upper bound $85$ . Keep or prune?

Recall Solution L1.2

Upper bound is the most optimistic (biggest) value inside the node: $85$ . That is greater than $70$ , so the subtree might hold something better. Keep it (insert into live set). Rule ::: For maximization, prune only when $upper_bound \leq incumbent$ . Here $85 > 70$ , so keep.

L1.3 Match each strategy to its data structure: FIFO B&B, LIFO B&B, Least-Cost B&B.

Recall Solution L1.3

FIFO B&B ::: Queue (BFS order — oldest node first) LIFO B&B ::: Stack (DFS order — newest node first) Least-Cost B&B ::: Priority queue (best bound first)

Level 2 — Application

Goal: turn the definitions into numbers.

L2.1 0-1 Knapsack, capacity $W = 10$ . Items (value, weight): A(40,2), B(30,5), C(50,10), D(10,5). Compute the root upper bound using the fractional-fill rule.

Recall Solution L2.1

Why fractional fill: allowing fractions relaxes the hard "0 or 1" constraint, so its optimum is always $\geq$ the integer optimum — a valid over-estimate. Densities $v_{i} / w_{i}$ : A $= 20$ , B $= 6$ , C $= 5$ , D $= 2$ . Order A, B, C, D.

Take A fully: profit $+ 40$ , weight used $= 2$ , capacity left $= 8$ .
Take B fully: profit $+ 30$ (total $70$ ), weight $= 7$ , capacity left $= 3$ .
C weighs $10$ but only $3$ fits → take fraction $\frac{3}{10} \cdot 50 = 15$ . $bound = 40 + 30 + 15 = 85.$ Answer ::: root upper bound $= 85$ .

L2.2 Same instance. Compute the bound of the node "exclude A" (A forced out; nothing else decided). Capacity still $10$ .

Recall Solution L2.2

A is gone, so fill from B, C, D in density order.

B fully: $+ 30$ , weight $5$ , capacity left $5$ .
C weighs $10$ , only $5$ fits → fraction $\frac{5}{10} \cdot 50 = 25$ . $bound = 30 + 25 = 55.$ Answer ::: exclude-A bound $= 55$ .

L2.3 A complete feasible solution ${A, B}$ has value $70$ and weight $7 \leq 10$ . After it becomes incumbent, is the exclude-A node (bound $55$ ) pruned?

Recall Solution L2.3

Incumbent $= 70$ (maximization). Exclude-A upper bound $= 55 \leq 70$ . Even its best case cannot beat $70$ . Verdict ::: Pruned — a whole subtree gone in one comparison.

Level 3 — Analysis

Goal: reason about why a bound is valid or an ordering is smart.

L3.1 For TSP with the cost matrix below (symmetric, cities 1–4), compute the 2-min lower bound. A " $-$ " is the diagonal (no self-loop).

1234 1 - 101520 210 - 3525 31535 - 30 4202530 -

Recall Solution L3.1

Why two cheapest edges per city: in any tour each city has exactly one edge in and one out, so it contributes at least its two smallest incident edges. Summing them over-counts each edge twice, hence the $\frac{1}{2}$ . Two cheapest incident edges per city:

City 1: $10, 15 \Rightarrow 25$
City 2: $10, 25 \Rightarrow 35$
City 3: $15, 30 \Rightarrow 45$
City 4: $20, 25 \Rightarrow 45$ Sum $= 25 + 35 + 45 + 45 = 150$ . Lower bound $= \frac{1}{2} (150) = 75$ . Answer ::: $LB = 75$ .

L3.2 Now force edge $1 - 2$ (cost $10$ ) into the tour. Recompute the 2-min lower bound. Should it be $\geq$ the previous bound? Explain.

Recall Solution L3.2

Forcing an edge removes freedom, so the bound can only rise or stay equal. City 1 must use edge $(1, 2) = 10$ as one of its two; its next cheapest is $15$ → contributes $25$ (unchanged, since $10, 15$ were already the two cheapest). City 2 must use $(1, 2) = 10$ ; next cheapest is $25$ → contributes $35$ (unchanged too). Cities 3, 4 unchanged: $45, 45$ . Sum $= 25 + 35 + 45 + 45 = 150$ , LB $= 75$ . Observation ::: LB stays $75$ here because edge $1 - 2$ was already among both cities' two cheapest; forcing it added no new constraint. The bound can only go up or stay — never down.

L3.3 Least-Cost (LC) B&B always expands the live node with the best bound. Argue why LC tends to find the optimum faster than FIFO or LIFO B&B.

Recall Solution L3.3

The bound is the most promising possible value inside a node. Expanding the best-bounded node first means we chase the region most likely to contain the true optimum, so we discover a strong incumbent early. A strong incumbent is a tighter threshold, which prunes more of the remaining tree. One-line reason ::: LC reaches a good incumbent sooner, and a good incumbent prunes harder — see A* Search for the same "best-first" idea with an admissible heuristic.

Level 4 — Synthesis

Goal: run a small tree end-to-end and combine moves.

L4.1 Run LC B&B on the knapsack of L2.1 ( $W = 10$ ; A(40,2), B(30,5), C(50,10), D(10,5)) until you can name the optimum and its value. Show which nodes get pruned.

Recall Solution L4.1

Order A, B, C, D by density. Incumbent starts at $0$ .

Root bound $= 85$ (L2.1). Branch on A.
Include A ( $p = 40, w = 2$ ): fill B fully ( $+ 30$ ), C fraction $\frac{3}{10} \cdot 50 = 15$ → bound $= 85$ .
Exclude A ( $p = 0, w = 0$ ): bound $= 55$ (L2.2).
LC picks Include-A (bound $85$ ). Branch on B.
- Include A,B ( $p = 70, w = 7$ ): C fraction $\frac{3}{10} \cdot 50 = 15$ → bound $= 85$ . D doesn't fit meaningfully.
- Include A, exclude B ( $p = 40, w = 2$ ): C fraction $\frac{8}{10} \cdot 50 = 40$ → bound $= 80$ .
Push toward completion of ${A, B}$ : remaining capacity $= 3$ ; C ( $10$ ) and D ( $5$ ) don't fit → complete solution ${A, B}$ , value $70$ , weight $7$ . Incumbent $= 70$ .
Now prune every live node with bound $\leq 70$ : Exclude-A (bound $55$ ) is killed. The Include-A/exclude-B node (bound $80 > 70$ ) survives but its best real completion is ${A, C} = 40 + 50 = 90$ ? Check weight: $2 + 10 = 12 > 10$ — infeasible; ${A, D} = 50$ , ${A} = 40$ — none beats $70$ , so it dead-ends without improving. Optimum ::: ${A, B}$ , value $70$ , weight $7 \leq 10$ .

L4.2 For the same instance, verify by brute force that $70$ really is optimal (list feasible subsets).

Recall Solution L4.2

Feasible subsets (weight $\leq 10$ ) and values:

${A, B}$ : w $7$ , v $70$
${A, C}$ : w $12$ ✗
${A, B, D}$ : w $12$ ✗
${A, D}$ : w $7$ , v $50$
${B, C}$ : w $15$ ✗
${C}$ : w $10$ , v $50$
${B, D}$ : w $10$ , v $40$
${A, B}$ ties nothing higher. Max feasible value ::: $70$ at ${A, B}$ — matches B&B. ✅

Level 5 — Mastery

Goal: design a bound and defend it.

L5.1 You must solve a minimization assignment: assign $n$ workers to $n$ jobs, cost matrix $c_{ij}$ , each worker one job. Propose a valid lower bound for a partial assignment (some workers already assigned) and prove it is optimistic.

Recall Solution L5.1

Bound design. Let $S$ = cost already committed by assigned workers. For each unassigned worker $i$ , add the minimum cost over jobs still free: $min_{j free} c_{ij}$ . $LB = S + \sum_{i unassigned} min_{j free} c_{ij} .$ Why optimistic (proof sketch): any completion assigns each unassigned worker $i$ to some free job at cost $\geq min_{j free} c_{ij}$ . Summing these minima can only under-count the true completion cost (it ignores the constraint that two workers can't share a job). So $LB \leq$ any real completion → valid lower bound for minimization. Prune when ::: $LB \geq incumbent$ .

L5.2 Numerically: with $2$ workers unassigned and free jobs having per-worker minimums $min = 7$ and $min = 9$ , and committed cost $S = 30$ , what is the bound? If the incumbent is $45$ , is the node pruned?

Recall Solution L5.2

$LB = 30 + 7 + 9 = 46.$ Incumbent $= 45$ (minimization). Since $46 \geq 45$ , the node's best case cannot beat what we hold. Verdict ::: $LB = 46$ , and $46 \geq 45 \Rightarrow$ pruned.

L5.3 Contrast this row-minimum bound with the Dynamic Programming / brute-force worst case. What does B&B actually improve?

Recall Solution L5.3

Row-minimum LB is cheap ( $O (n^{2})$ to compute) and prunes many partial assignments in practice. But if $c_{ij}$ are nearly equal, few nodes get pruned and B&B explores close to all $n!$ assignments. Takeaway ::: B&B improves the average/practical runtime through pruning; the worst case stays exponential ( $O (n!)$ here). It is a smarter exhaustive search, not a polynomial guarantee — see Big-O Notation.

Recall One-line self-test

Prune a node exactly when its ::: best-possible value (bound) cannot beat the incumbent — $\geq$ for minimization, $\leq$ for maximization.