---
title: Branch & Bound and Meet in the Middle
module: Backtracking & Search
moduleNumber: 9
lessonNumber: 3
order: 903
summary: |
  Plain backtracking prunes a search tree by _feasibility_; for _optimization_
  problems we can prune far more aggressively by _value_. **Branch and bound**
  keeps the best complete solution found so far and discards any partial solution
  whose optimistic bound cannot beat it. **Meet in the middle** splits the
  instance in two, enumerates each half, and recombines by binary search — turning
  $2^n$ into $O(2^{n/2}\,n)$ and pushing exact search out to $n \approx 40$.
topics: [Backtracking]
sources:
  - book: Skiena
    ref: "§ — Combinatorial Search / Heuristics"
  - book: CLRS
    ref: "Ch. 35 — Approximation (branch-and-bound context)"
  - book: Erickson
    ref: "Ch. — Backtracking"
practice:
  - title: 'Partition Array Into Two Arrays to Minimize Sum Difference'
    slug: partition-array-into-two-arrays-to-minimize-sum-difference
    difficulty: Hard
  - title: 'Closest Subsequence Sum'
    slug: closest-subsequence-sum
    difficulty: Hard
  - title: 'Maximum Score Words Formed by Letters'
    slug: maximum-score-words-formed-by-letters
    difficulty: Hard
  - title: 'Beautiful Arrangement'
    slug: beautiful-arrangement
    difficulty: Medium
---

The previous lessons built [**backtracking**](/algorithms/backtracking/backtracking-fundamentals):
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 often cuts the
running time by many orders of magnitude.

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 exponential running time, 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**.

> **Remark (Pruning rule).** At a node with bound $b$ and incumbent value $z^\ast$:
> if $b \le z^\ast$ (maximization) — or $b \ge z^\ast$ (minimization) — then _no_
> completion of this partial solution can improve on the incumbent, so prune the
> entire subtree. Otherwise branch on the next decision and recurse.

> **Proof (the prune is sound).** The bound is optimistic: $b$ is an over-estimate
> (maximization) of the best objective any completion of this node can achieve.
> So $b \le z^\ast$ means even the best descendant is no better than a solution we
> already hold, and discarding the entire subtree loses no improving solution. The
> minimization case is symmetric with $b \ge z^\ast$.[^erickson-bb] $\qed$

A bound is [sound](/algorithms/foundations/what-is-an-algorithm) exactly when this
holds — when it never prunes a subtree that contains an optimum. An optimistic bound
guarantees soundness, so branch and bound stays
[complete](/algorithms/foundations/what-is-an-algorithm) for the optimization
problem: the optimal solution survives every cut and is eventually reported. A bound
that could _under_-estimate (maximization) would be unsound, silently discarding the
answer.

The method's effectiveness depends entirely on 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.

> **Intuition.** Backtracking explores until a branch is _impossible_. Branch and
> bound explores until a branch is _pointless_. The incumbent is a moving
> floor; the bound is a ceiling on each subtree; whenever a subtree's ceiling
> drops below the floor, the subtree is pruned.

$$
% caption: Prune any node whose optimistic bound can't beat the incumbent
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=9mm, inner sep=1pt, font=\small},
  level distance=14mm, level 1/.style={sibling distance=34mm},
  level 2/.style={sibling distance=17mm}, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (r) {$42$}
    child {node[draw=acc, very thick] (a) {$40$}
      child {node (aa) {$31$}}
      child {node[draw=acc, very thick] (ab) {$38$}}
    }
    child {node[draw=red!75!black, text=red!75!black, dashed] (b) {$29$}
      child {node[draw=red!75!black, text=red!75!black, dashed] (ba) {$27$} edge from parent[draw=red!75!black, dashed]}
      child {node[draw=red!75!black, text=red!75!black, dashed] (bb) {$22$} edge from parent[draw=red!75!black, dashed]}
      edge from parent[draw=red!75!black, dashed]
    };
  \draw[acc, very thick] (r) -- (a);
  \draw[acc, very thick] (a) -- (ab);
  \node[draw=none, right=2mm of r, font=\footnotesize] {bound};
  \node[draw=none, font=\footnotesize, text=red!75!black] at (3.7,-1.4) {bound 29 $<$ best};
  \node[draw=none, font=\footnotesize, text=red!75!black] at (3.9,-2.8) {pruned};
  \node[draw=none, acc, font=\footnotesize] at (-4.2,-2.0) {\texttt{incumbent best = 38}};
\end{tikzpicture}
$$

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:

$$
\text{bound} \;=\; V \;+\; \sum_{i \in F_{\text{full}}} v_i
\;+\; \parens{c - \!\!\sum_{i \in F_{\text{full}}}\!\! w_i}\cdot \frac{v_j}{w_j},
$$

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, which is the optimism a sound bound requires.[^skiena-bb]

$$
% caption: The LP-relaxation bound: greedily fill remaining capacity $c$ in density order;
%          the overflowing item $j$ is sliced fractionally (the part beyond $c$ is the
%          relaxation's over-estimate)
\begin{tikzpicture}[
  >=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.4,1.55) rectangle (10.4,-1.6);
  % capacity bar outline (width c -> 6 units), height 0.8
  % whole items that fit: widths 2.2 and 1.8
  \fill[acc!15] (0,0) rectangle (2.2,0.8);
  \fill[acc!15] (2.2,0) rectangle (4.0,0.8);
  % fractional slice of item j inside capacity (width 2.0)
  \fill[acc!15] (4.0,0) rectangle (6.0,0.8);
  % capacity boundary
  \draw[acc, very thick] (6.0,-0.2) -- (6.0,1.0);
  \node[draw=none, acc, font=\footnotesize] at (6.0,1.25) {\texttt{capacity c}};
  % the overflow part of item j (beyond capacity) -- not actually taken (integrally)
  \draw[red!75!black, dashed] (6.0,0) rectangle (7.6,0.8);
  % item separators + labels
  \draw[black] (0,0) rectangle (6.0,0.8);
  \draw[black] (2.2,0)--(2.2,0.8);
  \draw[black] (4.0,0)--(4.0,0.8);
  \node[draw=none, font=\scriptsize] at (1.1,0.4) {item 1};
  \node[draw=none, font=\scriptsize] at (3.1,0.4) {item 2};
  \node[draw=none, font=\scriptsize, acc] at (5.0,0.4) {part of $j$};
  \node[draw=none, font=\scriptsize, text=red!75!black] at (6.8,0.4) {spills};
  % brackets / labels under
  \draw[black] (0,-0.25)--(0,-0.4)--(4.0,-0.4)--(4.0,-0.25);
  \node[draw=none, font=\footnotesize] at (2.0,-0.72) {\texttt{items that f\/it wholly}};
  \draw[acc] (4.0,-0.25)--(4.0,-0.4)--(6.0,-0.4)--(6.0,-0.25);
  \node[draw=none, font=\footnotesize, acc] at (5.0,-0.72) {\texttt{fractional value}};
  % the over-estimate callout
  \node[draw=none, font=\scriptsize, text=red!75!black, align=center] at (8.9,0.4)
    {\texttt{item j tail is}\\ \texttt{never taken}\\ \texttt{whole: bound}\\ \texttt{over-estimates}};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{KnapsackBnB}$ — maximize value within capacity $W$ (items sorted by $v_i/w_i$)
$z^\ast \gets 0$ // incumbent value
$\textsc{Expand}(i = 0,\ V = 0,\ \text{weight} = 0)$:
  if $\text{weight} > W$ then return // infeasible
  if $V > z^\ast$ then $z^\ast \gets V$ // new incumbent
  if $i = n$ then return
  if $\textsc{Bound}(i, V, \text{weight}) \le z^\ast$ then return // prune by value
  $\textsc{Expand}(i+1,\ V + v_i,\ \text{weight} + w_i)$ // take item $i$
  $\textsc{Expand}(i+1,\ V,\ \text{weight})$ // skip item $i$

$\textsc{Bound}(i, V, \text{weight})$:
  $b \gets V;\quad c \gets W - \text{weight}$
  for $j \gets i$ to $n-1$ do
    if $w_j \le c$ then $b \gets b + v_j;\ c \gets c - w_j$
    else return $b + c \cdot v_j / w_j$ // fractional fill
  return $b$
```

Branching on _take_ before _skip_ tends to find a heavy, valuable incumbent
early, which makes the bound bite sooner. Compare this against the
[**dynamic-programming**](/algorithms/dynamic-programming/knapsack) 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, heavily 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.**

$$
% caption: Knapsack B\&B ($W{=}6$; items
%          $A{:}\langle10,2\rangle,B{:}\langle12,4\rangle,C{:}\langle6,3\rangle$ by
%          density). The skip-$A$ node's LP bound $16\le z^*{=}22$, so that subtree is
%          pruned (red)
\begin{tikzpicture}[
  every node/.style={draw, align=center, minimum size=8mm, inner sep=3pt, font=\small},
  level distance=16mm,
  level 1/.style={sibling distance=46mm},
  level 2/.style={sibling distance=23mm},
  edgelbl/.style={draw=none, font=\scriptsize},
  dead/.style={fill=red!8, draw=red!70, dashed},
  edge from parent/.style={draw, ->, >=stealth}]
  \definecolor{acc}{HTML}{2348F2}
  \node {$V{=}0$\\$b{=}22$}
    child {node[draw=acc, very thick] {$V{=}10$\\$b{=}22$}
      child {node[fill=acc!15, draw=acc, very thick] {best 22\\ take A,B} edge from parent[draw=acc] node[edgelbl,left]{\texttt{take B}}}
      child {node {$V{=}10$\\$b{=}16$} edge from parent node[edgelbl,right]{\texttt{skip B}}}
      edge from parent[draw=acc] node[edgelbl,left]{\texttt{take A}}}
    child {node[dead] {$V{=}0$\\ $b{=}16$ dead}
      edge from parent[draw=red!70,dashed] node[edgelbl,right]{\texttt{skip A}}};
  \node[draw=none, align=left, font=\footnotesize, text=red!75!black] at (5.7,-2.0) {\texttt{bound 16} $<$ \texttt{best 22}\\ \texttt{pruned}};
\end{tikzpicture}
$$

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 $\tfrac23$ of $C$: $12 + 2\cdot\tfrac{6}{3} = 16$), which cannot beat
$22$, so the entire right half is discarded before a single completion is built.

::impl{algo="knapsack_branch_and_bound"}

### 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](/algorithms/sorting/heaps-and-heapsort) 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.

$$
% caption: Two search orders. Depth-first dives to a leaf for an early incumbent with
%          $O(n)$ stack; best-first expands the highest-bound live node — fewer
%          expansions, but an exponential frontier
\begin{tikzpicture}[
  >=stealth, font=\small,
  nd/.style={draw, circle, minimum size=6mm, inner sep=0},
  hl/.style={draw=acc, very thick},
  lbl/.style={draw=none, font=\scriptsize},
  edge from parent/.style={draw, ->, >=stealth}]
  \definecolor{acc}{HTML}{2348F2}
  \begin{scope}[level distance=11mm, level 1/.style={sibling distance=16mm}, level 2/.style={sibling distance=8mm}]
    \node[nd,hl] (df) at (0,0) {}
      child {node[nd,hl] {}
        child {node[nd,hl] {} edge from parent[draw=acc,very thick]}
        child {node[nd] {}}
        edge from parent[draw=acc,very thick]}
      child {node[nd] {}
        child {node[nd] {}}
        child {node[nd] {}}};
  \end{scope}
  \node[lbl] at (0,-4.0) {\texttt{depth-f\/irst: dive to leaf}};
  \node[lbl, acc] at (0,-4.7) {\texttt{early incumbent, O(n) memory}};
  \begin{scope}[xshift=58mm, level distance=11mm, level 1/.style={sibling distance=16mm}, level 2/.style={sibling distance=8mm}]
    \node[nd] (bf) at (0,0) {}
      child {node[nd,hl] {37}
        child {node[nd] {} edge from parent}
        child {node[nd] {}}
        edge from parent[draw=acc,very thick]}
      child {node[nd] {29}
        child {node[nd] {}}
        child {node[nd] {}}};
  \end{scope}
  \node[lbl] at (5.8,-4.0) {\texttt{best-f\/irst: expand top bound}};
  \node[lbl, acc] at (5.8,-4.7) {\texttt{fewer expansions, big frontier}};
\end{tikzpicture}
$$

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.

::impl{algo="best_first_knapsack"}

## 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 perform that
combination efficiently, 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)$.

```algorithm
caption: $\textsc{MeetInTheMiddle}$ — subset sum closest to target $T$
split items into halves $A$ (size $\lceil n/2\rceil$) and $B$
$S_A \gets$ all $2^{|A|}$ subset sums of $A$
$S_B \gets$ all $2^{|B|}$ subset sums of $B$
sort $S_B$
$best \gets \infty$
for each $a$ in $S_A$ do
  $r \gets T - a$ // complement from $B$
  $s \gets$ value in $S_B$ nearest $r$ (binary search: floor and ceiling of $r$)
  $best \gets \min(best,\ |\,a + s - T\,|)$
return $best$
```

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.

$$
% caption: $2^n \to O(2^{n/2})$ — enumerate each half, then binary-search the complement
\begin{tikzpicture}[
  cell/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=1pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw=none, font=\footnotesize] at (-1.3,0) {$S_A$:};
  \node[cell] (a0) at (0,0) {$0$};
  \node[cell] (a1) at (0.8,0) {$3$};
  \node[cell, draw=acc, very thick] (a2) at (1.6,0) {$5$};
  \node[cell] (a3) at (2.4,0) {$8$};
  \node[draw=none, font=\footnotesize] at (-1.3,-2.2) {$S_B$:};
  \node[cell] (b0) at (0,-2.2) {$1$};
  \node[cell] (b1) at (0.8,-2.2) {$4$};
  \node[cell, draw=acc, very thick] (b2) at (1.6,-2.2) {$6$};
  \node[cell] (b3) at (2.4,-2.2) {$9$};
  \node[draw=none, font=\footnotesize] at (5.0,-1.1) {target $T = 11$};
  \node[draw=none, font=\footnotesize] at (4.6,-2.2) {(sorted)};
  \draw[->, acc, very thick] (a2.south) .. controls (1.6,-1.1) and (1.6,-1.1) .. node[right, draw=none, font=\footnotesize] {\texttt{T - 5 = 6}} (b2.north);
  \node[draw=none, acc, font=\footnotesize] at (1.6,-3.0) {$5 + 6 = 11$};
\end{tikzpicture}
$$

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. To see the whole method end to
end, take the eight numbers $[3, 34, 4, 12, 5, 2, 1, 9]$ and target $T = 20$. Split
into $A = [3, 34, 4, 12]$ and $B = [5, 2, 1, 9]$. Enumerating every subset sum:

- $S_A = \{0, 3, 4, 7, 12, 15, 16, 19, 34, 37, 38, 41, 46, 49, 50, 53\}$ (the
  $2^4 = 16$ sums of $A$).
- $S_B = \{0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17\}$ (sorted).

Now walk $S_A$: for $a = 4$ we seek $T - a = 16$ in $S_B$, and $16$ is present, so
$4 + 16 = 20$ hits the target exactly — the subset $\{4\}$ from $A$ plus $\{2, 5,
9\}$ from $B$. The combine did $16$ binary searches of a $16$-element list instead
of scanning all $2^8 = 256$ subsets, and it scales: at $n = 40$ it is
$2^{20} \approx 10^6$ searches rather than $2^{40} \approx 10^{12}$ subsets.

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$.

::impl{algo="meet_in_the_middle"}

$$
% caption: Bidirectional search: two BFS frontiers of radius $d/2$ from $s$ and $t$ meet
%          in the middle, touching $\approx 2\,b^{d/2}$ nodes instead of one frontier of
%          $b^d$
\begin{tikzpicture}[
  >=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-2.6,2.2) rectangle (8.8,-2.6);
  % --- top: one-sided BFS, big disc of radius d ---
  \begin{scope}[shift={(-0.5,0.9)}, scale=0.42]
    \fill[red!12] (0,0) circle (3.0);
    \draw[red!75!black] (0,0) circle (3.0);
    \node[draw, circle, fill=acc!15, minimum size=4mm, inner sep=0, font=\scriptsize] at (0,0) {$s$};
    \node[draw, circle, minimum size=4mm, inner sep=0, font=\scriptsize] at (3.0,0) {$t$};
  \end{scope}
  \node[draw=none, font=\scriptsize, align=left, text=red!75!black] at (3.6,0.9)
    {\texttt{one frontier of radius d:}\\ \texttt{about b\^{}d nodes}};
  % --- bottom: two small discs of radius d/2 meeting ---
  \begin{scope}[shift={(-0.9,-1.4)}, scale=0.42]
    \fill[acc!15] (0,0) circle (1.6);
    \draw[acc] (0,0) circle (1.6);
    \fill[acc!15] (3.0,0) circle (1.6);
    \draw[acc] (3.0,0) circle (1.6);
    \node[draw, circle, fill=acc!15, minimum size=4mm, inner sep=0, font=\scriptsize] at (0,0) {$s$};
    \node[draw, circle, fill=acc!15, minimum size=4mm, inner sep=0, font=\scriptsize] at (3.0,0) {$t$};
    % meeting point
    \fill[acc] (1.5,0) circle (0.12);
  \end{scope}
  \node[draw=none, font=\scriptsize, align=left, acc] at (3.9,-1.4)
    {\texttt{two frontiers of radius d/2 meet:}\\ \texttt{about 2 b\^{}(d/2) nodes}};
\end{tikzpicture}
$$

::impl{algo="bidirectional_search"}

## 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 works best when a cheap, tight optimistic bound exists (knapsack's LP
fill, a [TSP](/algorithms/intractability/coping-with-hardness) node's spanning-tree
lower bound). Meet in the middle works best 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.

## How the world actually solves hard optimization

Branch and bound solves the
large integer programs behind logistics, scheduling, and network design every day.

**Branch and cut.** Modern integer-programming
solvers — CPLEX, Gurobi, the open-source SCIP — run **branch and cut**: branch and
bound whose LP-relaxation bound (exactly the knapsack bound of this lesson,
generalized) is tightened at each node by adding **cutting planes**, linear
inequalities valid for all integer solutions but violated by the current
fractional optimum.[^bandc] Gomory's cuts (1958) and the Padberg–Rinaldi cuts for
the traveling salesman turned instances once deemed hopeless into routine ones; a
combination of branch and cut solved a TSP over all $85{,}900$ cities of a VLSI
application to _proven_ optimality.[^tsp] The engineering lesson matches this
lesson's theory: a tighter bound (better cuts) and a stronger incumbent (better
heuristics) each prune more of the tree.

**A\*: the same idea.** Best-first branch and bound is, essentially,
the **A\*** search algorithm (Hart, Nilsson & Raphael, 1968): expand the live node
minimizing $f = g + h$, where $g$ is the cost so far and $h$ is an _admissible_
heuristic — a bound that never overestimates the remaining cost.[^astar]
Admissibility supplies the optimistic-bound condition that makes pruning sound
here; A\* is branch and bound with the objective "shortest path" and the bound
"heuristic-to-goal."

$$
% caption: The bound-tightening spiral of branch and cut. A cutting plane shaves the
%          fractional LP region toward the integer hull, lowering the optimistic bound at a
%          node; a stronger incumbent raises the floor. Where the two meet, the subtree is
%          pruned.
\begin{tikzpicture}[font=\small, >=stealth, yscale=0.9]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  % ceiling (bound) coming down, floor (incumbent) rising, toward a meeting
  \draw[->, thick] (0,0) -- (7.2,0) node[right, font=\footnotesize] {rounds};
  \draw[acc, very thick] (0.4,2.6) -- (2.2,2.2) -- (4.0,1.8) -- (5.8,1.55);
  \node[acc, font=\footnotesize, anchor=west] at (0.4,2.85) {bound (cuts tighten it down)};
  \draw[grn, very thick] (0.4,0.5) -- (2.2,0.8) -- (4.0,1.15) -- (5.8,1.4);
  \node[grn, font=\footnotesize, anchor=west] at (0.4,0.25) {incumbent (heuristics raise it)};
  \fill[black!70] (5.8,1.47) circle (2pt);
  \node[font=\footnotesize, anchor=west, black!70] at (5.95,1.47) {meet: prune / optimal};
\end{tikzpicture}
$$

**Meet in the middle in cryptanalysis.** The meet-in-the-middle split is older than
its algorithmic-puzzle use: Diffie and Hellman (1977) introduced it to attack
double encryption, showing that encrypting twice with two keys gives far less than
double the security because an attacker enumerates each key-half and matches in the
middle — the same $2^n \to 2^{n/2}$ collapse, applied to key search.[^mitm] The
subset trick and the cryptographic attack are the same idea.

## 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 **$\sqrt{}$ of it** at the cost of
  memory.

[^erickson-bb]: **Erickson**, Ch. — Backtracking: branch and bound as backtracking augmented with a value bound; the optimism of the bound is what makes pruning sound.
[^skiena-bb]: **Skiena**, § — Combinatorial Search / Heuristics: pruning a combinatorial search by bounding the best achievable completion, illustrated on knapsack-style problems.
[^bandc]: **Padberg, M. & Rinaldi, G.** (1991), "A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems," _SIAM Review_ 33(1), 60–100 — branch and bound tightened by cutting planes, the template of modern IP solvers; cutting planes trace to **Gomory, R. E.** (1958).
[^tsp]: **Applegate, D. L., Bixby, R. E., Chvátal, V. & Cook, W. J.** (2006), _The Traveling Salesman Problem: A Computational Study_, Princeton University Press — solving TSP instances with tens of thousands of cities to proven optimality by branch and cut.
[^astar]: **Hart, P. E., Nilsson, N. J. & Raphael, B.** (1968), "A formal basis for the heuristic determination of minimum cost paths," _IEEE Transactions on Systems Science and Cybernetics_ 4(2), 100–107 — A\* as best-first search with an admissible (optimistic) heuristic, i.e. branch and bound for shortest paths.
[^mitm]: **Diffie, W. & Hellman, M. E.** (1977), "Exhaustive cryptanalysis of the NBS data encryption standard," _Computer_ 10(6), 74–84 — the meet-in-the-middle attack on double encryption, the same $2^{n/2}$ split used for subset problems.