Branch & bound is exhaustive search made smart. You still explore a tree of every possible decision, but at each partial decision you compute an optimistic bound — the best score that branch could ever reach — and the moment that bound cannot beat a solution you already have, you throw the whole subtree away. It is brute force with a bouncer at the door.
Core idea. Branch on each choice (include / exclude an item), and at every node compute a bound:
an over-estimate of the best value still reachable below it. If bound <= best (the best complete
solution found so far), that node is hopeless — prune it and skip its entire subtree.
The classic vehicle is the 0/1 knapsack: pick a subset of items to maximize value without exceeding a weight capacity. With items A=(value 100, weight 2), B=(120, 3), C=(90, 3) and capacity W = 8, the best subset is all three (value 310, weight 8). Branch & bound finds it while visiting only 7 of the 15 possible nodes.
Intuition
Picture every item as a yes/no fork: include it or skip it. Stacked up, those forks form a binary tree, and a brute-force search would walk all 2^n leaves. That is wasteful — many branches are obviously doomed long before you reach a leaf.
The fix is a cheap, optimistic estimate at each node. For knapsack, sort items by value-per-weight and greedily fill the remaining capacity, allowing a fraction of the last item. That fractional fill can only over-state the truth, so it is a genuine upper bound. If even that rosy estimate does not exceed your current best, nothing below the node can help — prune it. The better your incumbent best, the more branches collapse, so descending the most promising branch first pays off quickly.
Walk through it
Step through the animation on the right. Each circle is a partial decision (+A = took A, −B = skipped B); its sublabel b=... is that node's bound. Two trackers on the side show the running best (incumbent) and the current node's bound.
We descend include-first. The root bounds at 310. Taking A, then B, then C reaches a full feasible leaf worth 310 with weight exactly 8 — so best climbs 100 → 220 → 310. Now the pruning earns its keep. Backtracking to try excluding C gives a bound of only 220; since 220 ≤ 310, that node turns red and is pruned. Excluding B bounds at 190 ≤ 310 — pruned. And the entire exclude-A branch bounds at 210 ≤ 310, so one comparison prunes a whole subtree without ever inspecting B or C inside it. Seven nodes touched instead of fifteen.
The code, line by line
items = [(100, 2), (120, 3), (90, 3)] # sorted by value/weight
W, best = 8, 0
def bound(i, profit, weight):
b, w = profit, weight
while i < len(items) and w + items[i][1] <= W:
w += items[i][1]; b += items[i][0]; i += 1
if i < len(items):
b += (W - w) * items[i][0] / items[i][1]
return b
def dfs(i, profit, weight):
global best
if weight > W or bound(i, profit, weight) <= best:
return # prune
best = max(best, profit)
if i == len(items):
return
dfs(i + 1, profit + items[i][0], weight + items[i][1])
dfs(i + 1, profit, weight)bound()is the optimistic estimate: greedily take whole items while they fit (lines 6–7), then add a fraction of the next item to top off the leftover capacity (lines 8–9). Fractions are allowed only here, which is what makes it an upper bound on the real 0/1 answer.- Line 14 is the heart of it: a node dies if it is either infeasible (
weight > W) or hopeless (bound <= best). Either way line 15 returns, skipping both recursive calls below. - Line 16 records any complete-or-partial profit that improves the incumbent — a stronger
bestprunes more aggressively later. - Lines 19–20 branch: first include item
i(descend the promising side), then exclude it. Going include-first finds a strongbestearly, so the exclude side is more likely to be pruned.
Complexity
| Case | Time | Notes |
|---|---|---|
| Best | O(n) (moderate) | tight bounds prune nearly every branch; one deep path plus prunes |
| Worst | O(2^n) (slow) | weak bounds prune nothing — degenerates to full enumeration |
O(n) (moderate)Branch & bound never changes the worst case — a pathological instance can still force you to visit every node. What it changes is the typical case: a good bound function lets you skip enormous swaths of the tree, often turning an intractable search into a fast one. The space is O(n) for the recursion depth (the current root-to-node path).
When to use / pitfalls
Reach for branch & bound on optimization problems where you can write a cheap, valid bound — knapsack, travelling salesman, job assignment, integer programming. The interview signal: NP-hard optimization, small-to-moderate input, and an obvious relaxation (drop the integrality, allow fractions, ignore a constraint) that gives an over-estimate for maximization. Mention that include-first ordering and a strong initial incumbent make pruning bite harder.
Two traps. First, the bound must be admissible in the right direction: for a maximization problem it
must never under-estimate, or you will prune the actual optimum. Second, get the prune test right — use
bound <= best (a node tying the incumbent cannot improve it), but if you need to keep ties, switch to
bound < best. And remember the worst case is still exponential: branch & bound is a heuristic speedup,
not a complexity guarantee.
Practice
After the search finds the leaf worth 310 (take A, B, C), why is the entire exclude-A subtree pruned with a single check?
1. What must be true about the bound function for a maximization problem?
2. Why does the knapsack bound allow taking a fraction of an item?
3. When is a node pruned in the dfs?
4. What is the worst-case time complexity of branch & bound?