Branch and Bound

Branch and bound (B&B) is a design paradigm for combinatorial optimization: problems that ask for the best member of a finite (but astronomically large) set of feasible solutions, according to some objective function (minimize cost, maximize profit, etc.). The search space is organized as a tree, where the root represents "no decisions made yet," each internal node represents a partial solution (some decisions fixed, others still open), and each leaf represents a complete solution. Branching is the act of splitting a node into children by fixing the next undetermined decision variable, exactly as in ordinary backtracking. What distinguishes branch and bound from plain backtracking is the bounding function, $B(\cdot)$, computed at every node. For a minimization problem, $B(n)$ is a lower bound on the objective value of any complete solution reachable by extending the partial solution at node $n$. The algorithm also maintains an incumbent: the best complete, feasible solution discovered so far, with objective value $z^*$. The central pruning rule is:

The logic is airtight: since $B(n)$ is a valid lower bound on everything below $n$, and the incumbent already achieves $z^*$, nothing below $n$ can improve on the incumbent. We are not guessing that the branch is unpromising — we have a mathematical certificate that it is. This is what separates branch and bound from heuristic pruning: the bound must be provably optimistic (a lower bound for minimization, an upper bound for maximization), or the method silently loses correctness. Two ingredients therefore determine how well B&B performs on a given problem: how tight the bound is (a bound closer to the true optimum prunes more) and the order of exploration (which node to expand next, since finding a strong incumbent early enables earlier pruning elsewhere). These two axes — bound quality and search strategy — are the entire design space of branch and bound, and the rest of this article develops both.

Setting up the tree. As in backtracking, we pick an order of decision variables $x_1, x_2, \dots, x_n$ (e.g., "include item $i$ in the knapsack or not," "assign job $j$ to machine $k$ or not"). A node at depth $d$ fixes $x_1,\dots,x_d$ and leaves the rest free. Its children fix $x_{d+1}$ to each of its possible values.

The bounding function. At each node, before branching further, we compute $B(n)$: an easily-computed relaxation of the problem restricted to the fixed choices. Common relaxation techniques:

• Linear/LP relaxation: drop integrality constraints (e.g., allow a fractional amount of an item in knapsack) and solve the resulting continuous problem, which is easy (polynomial time) and gives an upper bound (for maximization) on the integer problem.
• Greedy/fractional bound: e.g., in 0/1 knapsack, fill remaining capacity by value density, allowing the last item to be fractional — this reproduces the classical fractional-knapsack bound used to prune the exact integer search.
• Combinatorial relaxation: e.g., in the traveling salesman problem, replace "must form one cycle" with "each city has degree 2" (a 1-tree or assignment-problem relaxation), which is solvable fast and never worse than the true tour cost.

The main loop. We maintain a live list (a set of nodes not yet processed) and the incumbent value $z^*$ (initialized to $-\infty$ for maximization, or $+\infty$ for minimization, or to the value of some quick heuristic solution to start pruning immediately). We repeatedly select a live node, bound it, and either prune it, replace the incumbent (if it is itself a complete, feasible, improving solution), or branch it into children which join the live list. ``` function BRANCH-AND-BOUND(root, maximize=True): incumbent ← None incumbent_value ← -infinity if maximize else +infinity live ← {root} // priority queue or stack while live is not empty: n ← SELECT-AND-REMOVE(live) // strategy-dependent if n is INFEASIBLE: continue // prune: dead branch bound ← BOUND(n) // cheap optimistic estimate // Pruning test: can n possibly beat the incumbent? if maximize and bound ≤ incumbent_value: continue // prune: cannot improve if not maximize and bound ≥ incumbent_value: continue // prune: cannot improve if n is a COMPLETE solution: if IS-BETTER(n.value, incumbent_value, maximize): incumbent, incumbent_value ← n, n.value continue for child in EXPAND(n): // branch on next variable live.insert(child) return incumbent, incumbent_value ``` `SELECT-AND-REMOVE` encodes the exploration strategy:

• Depth-first branch and bound (DFBB): `live` is a stack (or implemented via recursion). Memory is $O(\text{depth})$, matching plain backtracking, and a complete feasible solution — an anytime answer — is available early and steadily improved.
• Best-first branch and bound (BFBB): `live` is a priority queue ordered by bound (most promising bound first). This tends to find near-optimal incumbents very quickly and prune enormous portions of the tree early, but the live list can grow to hold exponentially many nodes, costing more memory.
• Hybrids: many practical solvers use best-bound-first with depth-first dive: dive greedily to find incumbents fast, then switch to best-first once the tree is partially explored — this is essentially what production MIP solvers do.

The `BOUND` function is problem-specific; for 0/1 knapsack, with items sorted by value/weight ratio, a partial assignment's bound is the value already accumulated plus the fractional-knapsack value obtainable from remaining items and remaining capacity. This is precisely the greedy relaxation from the fractional knapsack problem, repurposed as a pruning oracle rather than as a final answer.

Correctness. The proof rests on one invariant maintained throughout the algorithm: > Invariant: at every point during execution, the true optimal solution's value is either already stored as `incumbent_value`, or it lies within the subtree rooted at some node still in `live`. Initially this holds trivially: the optimum, wherever it is, lies in the subtree rooted at `root`, which is in `live`. Each iteration either (a) discovers a complete feasible solution and updates the incumbent if it improves, which preserves the invariant since that leaf's own subtree is now "accounted for"; or (b) prunes a node $n$ because $B(n)$ is no better than `incumbent_value`. This is safe precisely because $B(n)$ is a valid bound: it means every completion within $n$'s subtree has objective at least as bad as (or equal to) the incumbent, so the optimum cannot be strictly inside that subtree unless it ties the incumbent, in which case the incumbent already represents an optimal value; or (c) branches $n$ into children whose union of subtrees is exactly $n$'s subtree (since branching is a case split over the next decision variable), so the invariant transfers from $n$ to its children. When `live` becomes empty, every subtree has either been fully explored (its leaves compared against the incumbent) or pruned with a certificate that it holds nothing better. By the invariant, the optimum must therefore equal `incumbent_value`. This argument requires two conditions to hold: the bounding function must be a valid relaxation bound (never worse than what any completion can achieve), and branching must be exhaustive and non-overlapping for the invariant's transfer step to be valid.

Time complexity. In the worst case, no pruning occurs and B&B degenerates to exhaustive backtracking search: if there are $n$ binary decision variables, the tree has up to $2^{n+1}-1$ nodes, and with $O(1)$ or $O(n)$ work to compute a bound per node, worst-case time is $O(2^n \cdot p(n))$ for some polynomial $p$ (the per-node bounding cost). Branch and bound does not change the worst-case complexity class of an NP-hard problem — it remains exponential in the worst case, since a polynomial worst-case bound would imply P = NP for NP-hard optimization problems (assuming standard complexity assumptions). What changes, often dramatically, is the typical number of nodes actually visited, because tight bounds prune large subtrees wholesale rather than enumerating them leaf by leaf. Empirically, for well-bounded formulations (tight LP relaxations, good variable-ordering heuristics), B&B routinely solves instances with hundreds or thousands of variables that a naive $2^n$ enumeration could never touch, though pathological instances still exist where pruning is minimal.

Space complexity. Depth-first B&B uses $O(d)$ space where $d$ is the tree depth (typically $O(n)$), since only the current root-to-node path plus siblings need to be retained — matching ordinary backtracking. Best-first B&B can require space proportional to the number of live nodes simultaneously held in the priority queue, which in the worst case is exponential, trading memory for the tendency to find strong incumbents (and hence prune) sooner. This is the classic time–memory tradeoff between the two exploration strategies, and it is why many industrial solvers default to depth-first or hybrid strategies rather than pure best-first.

Honesty about tradeoffs. The performance of B&B is only as good as its bounding function. A loose bound (far from the true optimum) prunes little and the method degrades toward brute force; a bound that is expensive to compute per node can dominate runtime even if it prunes well. Designing a good bound is often the hardest and most problem-specific part of applying this paradigm — there is no free lunch, and this is exactly why real solvers invest heavily in relaxations (LP relaxations, Lagrangian relaxations, semidefinite relaxations) tailored to each problem family.

Consider a 0/1 knapsack instance with capacity $W = 10$, and four items sorted by value density $v_i/w_i$ (a prerequisite step, as in fractional knapsack):

We maximize total value subject to $\sum w_i \le 10$. The bound at a node with items $\{1,\dots,d\}$ decided (chosen value $V$, weight used $w$, remaining capacity $R = 10-w$) is the fractional-knapsack upper bound: take remaining items greedily by density, allowing the last one taken to be fractional.

Root (no decisions): greedily fill capacity 10 by density — take A (4, value 12, remaining cap 6), take B (5, value 10, remaining cap 1), then $1/3$ of C (value $1.67$). Bound $= 12+10+1.67 = 23.67$. `incumbent_value = -∞` (or seed with a quick greedy integer solution, value 22, from A+B+ (skip C, D since they don't fit) — let's seed incumbent at 22 for a faster trace).

Branch on A (include/exclude):

• A = 1 (weight 4, value 12, remaining cap 6): bound = $12 + \text{frac-fill}(6 \text{ over } B,C,D)$. Take B (5, val 10, cap left 1), then $1/3$ of C: $12+10+1.67=23.67$. Live, bound $> 22$.
• A = 0 (weight 0, value 0, remaining cap 10): bound = frac-fill(10 over B, C, D) = B(5,10)+C(3,5)+ then 2/6 of D = $10+5+3.0 = 18.0$. Since $18.0 \le 22$, prune — this whole branch, and everything under "exclude A," is discarded without ever considering B, C, or D individually along it.

Already, roughly half the tree (all subtrees under $A=0$) vanishes in one comparison.

Continue under A = 1, branch on B:

• A=1, B=1 (weight 9, value 22, remaining cap 1): bound = $22 + \text{frac-fill}(1 \text{ over } C, D)$. Only room for $1/3$ of C: $22 + 1.67 = 23.67$. Live.
• A=1, B=0 (weight 4, value 12, remaining cap 6): bound = $12 + \text{frac-fill}(6 \text{ over } C, D)$ = C(3,5) fully, then $3/6$ of D (val 4.5): $12+5+4.5=21.5$. Since $21.5 \le 22$, prune.

Continue under A=1, B=1, branch on C (remaining cap 1, C weighs 3 — infeasible to include):

• C=1: infeasible (weight would be $9+3=12>10$) — prune as infeasible.
• C=0 (weight 9, value 22, remaining cap 1): bound = $22 + \text{frac-fill}(1 \text{ over } D)$. D weighs 6, so only $1/6$ of D: $22 + 1.5 = 23.5$. Still $>22$, must branch on D.

Branch on D (remaining cap 1, D weighs 6 — infeasible to include):

• D=1: infeasible, prune.
• D=0: complete solution, weight 9, value 22. Compare to incumbent (22): tied, not strictly better, discard as a duplicate optimum (or accept as an alternate optimal solution, per implementation choice).

At this point `live` is empty (every branch has been pruned or exhausted), so the algorithm terminates with `incumbent_value = 22`, achieved by $\{A, B\}$. Out of $2^4 = 16$ possible leaf assignments, the algorithm generated on the order of 7 internal nodes and evaluated only 2 complete leaves explicitly — the rest were eliminated by the bound before ever being enumerated. This is the essential empirical payoff of branch and bound: exponential search space, near-linear number of nodes actually touched, on a well-structured instance.

Branch and bound emerged from operations research in the 1960s, as researchers sought exact methods for integer and combinatorial optimization problems that defied both closed-form solutions and pure enumeration. The name itself, and the first general formalization applied to the traveling salesman problem, is credited to Ailsa Land and Alison Doig, whose 1960 paper on integer programming introduced the branching-and-bounding structure used essentially unchanged in modern solvers.

The paradigm's staying power comes from its generality: any problem whose feasible region can be split into cases and whose relaxations are tractable admits a branch-and-bound treatment, which is why it remains the backbone of exact combinatorial optimization six decades after its introduction.

Commercial mixed-integer programming solvers — CPLEX, Gurobi, SCIP, CBC — are, at their core, industrial-strength branch-and-bound engines, augmented with cutting planes (branch-and-cut) and column generation (branch-and-price). These solvers underpin airline crew scheduling, supply-chain and vehicle-routing optimization, portfolio construction under discrete constraints, and chip-placement and VLSI design, where the decision variables are inherently discrete (assign, route, place) and exact optimality guarantees are valuable, not just approximate heuristics. Compilers and constraint solvers use branch and bound (often under the name "constraint propagation with pruning") for register allocation and instruction scheduling subproblems where an optimal assignment within a small search space is worth computing exactly. Game-tree search in classical AI — exemplified by alpha-beta pruning in chess and other perfect-information games — is a close cousin of branch and bound, using a similar "prune once you know this branch cannot change the outcome" logic, though there the bound comes from adversarial minimax reasoning rather than a relaxation. The traveling salesman problem, still one of the most-studied NP-hard problems, has been solved exactly for instances with tens of thousands of cities using branch-and-bound/branch-and-cut hybrids — a testament to how far intelligent pruning can push exact methods beyond what naive complexity bounds would suggest is practical. Where instance sizes grow beyond what even excellent bounds can tame, practitioners often turn to approximation algorithms or, as previewed by Introduction to Randomized Algorithms, randomized and metaheuristic methods that trade the guarantee of optimality for tractable running time.

Ask the tutor: How would you design and prove a valid bounding function for a new combinatorial optimization problem you have not seen before?