Branch and bound: Visual walkthrough — Coding deep dive

Step 1 — What are we even choosing?

WHAT. We have a bag that holds a total weight of $W = 10$ . Each item is either taken (1) or left behind (0) — no cutting items in half. We want the biggest total value that still fits.

WHY start here. Before we can prune anything, we must picture the space of all choices. Every item is one yes/no switch. Four switches means $2^{4} = 16$ possible bags. Branch and Bound is a way to avoid checking all 16 — but first, look at all 16.

PICTURE. The tree below: each level flips one switch. A full root-to-leaf path is one complete bag.

Checking every leaf is Backtracking's territory — legal but slow. We want to skip subtrees. To skip safely, we need a number.

Step 2 — What number do we need at each node?

WHAT. At a half-finished node we already carry a known profit $p$ and used weight $w$ . We invent a number called the bound: the most value this node could possibly reach if we finished it in the luckiest legal way.

WHY. If the luckiest possible finish of this node is still worse than a complete bag we already hold (the incumbent), then finishing this node is pointless. One comparison kills a whole subtree. But this only works if the bound is a guaranteed over-estimate — if it ever under-estimated, the true best answer could hide in a branch we wrongly deleted.

PICTURE. The bound is a ceiling drawn above the node: every real completion lives under it.

So the whole game is: find a ceiling that is easy to compute yet never lies.

Step 3 — Relax the hard rule to get an easy ceiling

WHAT. The rule "each item is 0 or 1" is what makes the problem hard. We relax it: pretend we may take fractions of an item — 0.3 of item C is allowed.

WHY this tool and not another. We could guess a ceiling randomly, but random guesses can lie. A relaxation (removing a constraint) is guaranteed safe: giving yourself more freedom can never lower the best achievable value. So

$best_{fractional} \geq best_{integer} .$

The fractional best is a legitimate over-estimate — exactly the safe ceiling we needed in Step 2. And it happens to be easy to compute (Step 4).

PICTURE. Item C as a solid brick (0/1) versus a pourable liquid (fractional). Liquid always fills the bag at least as well.

Step 4 — Solve the easy version greedily (value-density)

WHAT. Sort items by value-density $\frac{v _{i}}{w _{i}}$ (value per kilo). Pour them into the bag in that order until it's full; the last item may go in as a fraction.

WHY. For the fractional problem, greedy is provably optimal (exchange argument: swapping any bit of a denser item for a lighter-density one can only help). Density answers the question "per unit of scarce capacity, who pays the most value?" — precisely what a weight-limited bag cares about.

Densities: $A = \frac{40}{2} = 20$ , $B = \frac{30}{5} = 6$ , $C = \frac{50}{10} = 5$ , $D = \frac{10}{5} = 2$ . Order: A, B, C, D.

PICTURE. A vertical capacity bar of height 10 being filled A → B → then a slice of C.

Root fill: A (w 2, +40) → B (w 5, +30, total weight 7) → C needs 10 but only 3 capacity left, so take fraction $\frac{3}{10}$ of C: $+ \frac{3}{10} \cdot 50 = 15$ .

$root bound = A 40 + B 30 + slice of C \frac{3}{10} \cdot 50 = 85$

$40, 30$ — whole items that fit
$\frac{3}{10}$ — leftover capacity $\div$ that item's weight $= 3/10$
$50$ — full value of C, scaled by the fraction

Step 5 — The bound at any node

WHAT. At a node we've decided some items already: carried profit $p$ , used weight $w$ , remaining capacity $c = W - w$ . Continue the greedy fill using only the still-undecided items, in density order.

WHY. The decided part $p$ is fixed and real. The undecided part is a smaller fractional knapsack — solve it greedily exactly as before. The sum is the ceiling for this node.

PICTURE. A node's bar split into a solid "already decided" base (height $w$ , value $p$ ) topped by the greedy fractional fill of the remaining capacity $c$ .

Step 6 — Branch, compare, prune

WHAT. From the root, branch on the densest item A. Compute a bound for each child. Whenever a child is a complete bag, its value may become the new incumbent. Any node whose bound $\leq$ incumbent is deleted.

WHY branch on A first. A drives the biggest bound, so exploring it fast tends to find a strong incumbent early — and a strong incumbent prunes more later. (Least-Cost B&B always pops the best-bound live node.)

PICTURE. Two children of the root with their bounds; the loser branch struck out.

Include A ( $p = 40, w = 2$ ): fill B whole (+30, w 7), then C slice $\frac{3}{10} \cdot 50 = 15$ → bound 85.
Exclude A ( $p = 0, w = 0$ ): fill B whole (+30, w 5), then C slice $\frac{5}{10} \cdot 50 = 25$ → bound 55.

Diving down include-A eventually yields a real bag {A, B} with value $70$ → incumbent $= 70$ .

Now the exclude-A node has bound $55$ . Compare:

$best possible below exclude-A 55 \leq incumbent 70 \Rightarrow prune.$

An entire half of the tree dies in one comparison — provably safe, because 55 is a true ceiling and can never beat 70.

Step 7 — The degenerate & edge cases you must not trip on

WHAT / WHY / PICTURE — four corners that break naïve code:

The one-picture summary

The full pipeline: decide (node) → relax to fractions → greedy fill by density → ceiling number → compare to incumbent → keep or prune.

Recall Feynman: retell the whole walkthrough

I want the most valuable bag I can carry, and each thing is all-or-nothing. Trying every combination is slow, so at each half-packed stage I ask: "If I got to cheat and pour things like liquid, what's the best I could pour into what's left?" I pour the richest-per-kilo stuff first, slicing the last item to top it off — that gives me a number that is always at least as good as the real best finish. If that dreamy number is still worse than a real bag I already packed, I toss this whole line of choices without finishing it, and I know I lost nothing, because the number never lied downward. Do this over the branching yes/no tree and huge chunks vanish with a single comparison. Flip "biggest / ceiling / prune-if-too-low" to "smallest / floor / prune-if-too-high" and the very same machine solves shortest tours.

Recall Quick self-test

Why must the bound be optimistic, not just any estimate? ::: A pessimistic estimate could sit below a branch's true optimum, so "even the best case is bad" stops being a proof — you'd prune the branch holding the real answer and get a wrong result. In the run, why was the exclude-A branch (bound 55) safe to delete? ::: 55 is a guaranteed ceiling on everything inside it; the incumbent was already 70; since $55 \leq 70$ nothing there can beat 70. What's the one line that handles minimization instead? ::: Use a lower bound (floor) and prune when $LB \geq incumbent$ .

See also: ← back to the topic note · 0-1 Knapsack · Backtracking · Greedy Algorithms · A* Search · Big-O Notation