Branch & Bound and Meet in the Middle

The previous lessons built backtracking: a depth-first walk over a tree of partial solutions that prunes a branch the moment it becomes infeasible, such as a queen attacking another or a graph coloring conflict. That kind of pruning asks a yes/no question: can this partial solution still be completed at all? For optimization problems, maximize this or minimize that, we can ask a sharper question: even in the best case, can completing this partial solution beat the best answer I already have? If not, the entire subtree is dead, feasible or not. Pruning by value rather than mere feasibility is the idea behind branch and bound, and it is often the difference between minutes and millennia.

When even aggressive pruning is not enough, when the search tree is genuinely $2^n$-shaped and $n$ is, say, $36$, a second technique buys a square root of the running time outright. Meet in the middle splits the instance, enumerates each half independently, and stitches the halves back together with sorting and binary search. Both techniques attack the same enemy, the exponential, from different sides.

Branch and bound: pruning by value

Branch and bound is backtracking with two extra pieces of bookkeeping. The first is the incumbent: the value (and witness) of the best complete solution found anywhere in the search so far. The second is a bound computed at every node, an optimistic estimate of the best objective achievable by any completion of that partial solution. For a maximization problem the bound is an upper bound (no completion can do better than this); for minimization it is a lower bound.

Correctness is immediate: the bound is optimistic, so $b\le z^{\ast }$ means even the best descendant is no better than a solution we already hold; discarding it loses nothing.¹ The power of the method lives entirely in two design choices. A tighter bound prunes more nodes; a bound equal to the true optimum would prune everything but the answer. And a better search order, finding a strong incumbent early, raises $z^{\ast }$ sooner, which retroactively prunes more of the tree. The two interact: a good incumbent makes a mediocre bound effective.

The right subtree carries bound $29\le z^{\ast }=38$, so it is pruned without ever being expanded; the blue path is the active best completion that established the incumbent.

Worked example: 0/1 knapsack by branch and bound

We have $n$ items with values $v_i$ and weights $w_i$ and a capacity $W$; choose a subset of maximum total value with total weight $\le W$. The decision tree is binary, take item $i$ or skip it, so it has $2^n$ leaves. To bound a node, we use the LP relaxation: relax the integrality constraint and allow a fraction of the next item. First order all items by value density$v_i/w_i$, descending. At a node that has fixed a prefix of decisions, with accumulated value $V$ and remaining capacity $c$, greedily fill $c$ with the not-yet-decided items in density order, taking the last one fractionally:

where $F_{\text{full}}$ are the remaining items that fit wholly and $j$ is the first item that overflows (filled fractionally). This fractional fill is the optimal solution to the relaxed problem, so it can only over-estimate the integral optimum, exactly the optimism a bound needs.²

Branching on take before skip tends to find a heavy, valuable incumbent early, which makes the bound bite sooner. Note what this buys us against the dynamic-programming solution. The DP runs in $\Theta (nW)$ time, pseudo-polynomial, because $W$ enters as a magnitude, not a bit-length. When $W$ is enormous (say weights are $9$-digit numbers) the DP table is hopeless, yet if $n$ is moderate the branch-and-bound tree, ferociously pruned, finishes quickly. The two methods are complementary: DP wins when $W$ is small; branch and bound wins when $W$ is huge but $n$ is moderate.

Branching take-first dives straight to the incumbent $\{A,B\}$ with value $z^{\ast }=22$. The skip-$A$ subtree's optimistic LP bound is only $16$ (take $B$ whole, then $\frac{2}{3}$ of $C$: $12+2\cdot \frac{6}{3}=16$), which cannot beat $22$, so the entire right half is discarded before a single completion is built.

Search order: depth-first vs best-first

The skeleton above is depth-first branch and bound: it recurses to a leaf fast, so it finds some complete solution, an incumbent, almost immediately, and it uses only $O(n)$ stack. The cost is that the first incumbent may be poor, weakening early pruning. The alternative is best-first search: keep a priority queue of live nodes keyed by their bound, and always expand the node with the most promising bound. Best-first tends to drive toward the optimum with the fewest expansions and, for many problems, expands the optimal node first, but it can hold an exponential frontier of live nodes in the queue, so its memory is the liability. The practical compromise is to seed the incumbent with a quick greedy solution, then run depth-first with strong bounds: cheap memory, and a floor high enough that the bound prunes hard from the start.

Depth-first (left) follows one accented path to a leaf, banking an incumbent fast while holding only the current root-to-node stack. Best-first (right) instead pops the live node of highest bound ($37>29$) from a priority queue, steering toward the optimum in fewer expansions at the cost of keeping the whole frontier in memory.

Meet in the middle

Some problems resist pruning entirely: the bound is weak, the structure symmetric, every branch genuinely live. If the instance is a subset problem over $n$ items and $n\le 40$, meet in the middle sidesteps pruning and attacks the exponent directly. Split the items into two halves $A$ and $B$ of size $\approx n/2$. Enumerate all $2^{n/2}$ subset sums of $A$ into a list $S_A$, and likewise all subset sums of $B$ into $S_B$. Every subset of the whole is one choice from $A$ paired with one from $B$, so the full answer is recovered by combining one element of $S_A$ with one of $S_B$, but we do that combination cleverly, not by trying all $2^{n/2}\cdot 2^{n/2}=2^n$ pairs.

For the canonical task, find a subset whose sum is closest to a target $T$ (this is the minimum-partition-difference problem with $T=({\sum }_i{x}_i)/2$), sort $S_B$, then for each $a\in S_A$ binary-search $S_B$ for the value nearest $T-a$. Each query is $O(\log 2^{n/2})=O(n)$, so the whole combine is $O(2^{n/2}n)$.

The enumeration is $O(2^{n/2})$ per half, the sort is $O(2^{n/2}n)$, and the combine is $O(2^{n/2}n)$, so the whole algorithm is $O(2^{n/2}n)$, a quadratic improvement over the $O(2^n)$ brute force. Concretely, $2^{40}$ is about $10^{12}$ (out of reach) while $2^{20}$ is about $10^6$ (instant). The technique is exact, no approximation and no pruning luck, and it is the intended solution to every Hard subset problem in this lesson's practice set.

For each sum $a$ on the top we binary-search the sorted bottom list for $T-a$; the blue pair $5+6=11$ hits the target exactly. The same split-and-recombine idea is the graph analog bidirectional search: to find a shortest path, run BFS forward from the source and backward from the target simultaneously and stop when the two frontiers meet, exploring $\approx 2\cdot b^{d/2}$ nodes instead of $b^d$.

When to reach for which

The three pruning disciplines line up neatly along one axis: what justifies discarding a branch.

• Backtracking prunes by feasibility: a partial solution that violates a constraint can never be completed, so cut it.
• Branch and bound prunes by value: a partial solution whose optimistic bound cannot beat the incumbent is pointless to complete, so cut it.
• Meet in the middle prunes nothing; it instead trades exponential time for the square root of it, $2^n\to 2^{n/2}$, paying with $O(2^{n/2})$ memory to store the enumerated half.

Branch and bound shines when a cheap, tight optimistic bound exists (knapsack's LP fill, a TSP node's spanning-tree lower bound). Meet in the middle shines when no such bound exists but $n$ is small enough that $2^{n/2}$ is affordable. Both are exact; neither changes the worst-case exponential complexity; both routinely turn an infeasible instance into a feasible one.

Takeaways

• Branch and bound is backtracking for optimization: maintain an incumbent (best complete solution so far) and a bound (optimistic estimate per node), and prune any node whose bound cannot beat the incumbent.
• The method's power is all in the bound tightness and search order: a tighter bound and an earlier strong incumbent each prune more of the tree.
• For 0/1 knapsack, order by density $v_i/w_i$ and bound by the LP-relaxation fractional fill; branch and bound beats the $\Theta (nW)$ DP when $W$ is huge but $n$ is moderate.
• Depth-first branch and bound finds an incumbent fast with $O(n)$ memory; best-first (priority queue on bound) targets the optimum with fewer expansions but can hold an exponential frontier.
• Meet in the middle enumerates each of two halves ($2^{n/2}$ subset sums) and recombines by sorting + binary search, giving $O(2^{n/2}n)$, exact search up to $n\approx 40$; bidirectional search is the graph analog.
• One axis: backtracking prunes by feasibility, branch and bound by value, meet in the middle trades exponential time for ​ of it at the cost of memory.