Branch and Bound

Backtracking for optimisation: maintain the best solution found so far (the incumbent), and prune any branch whose optimistic bound cannot beat it.

The skeleton

long long best = INF;                                   // incumbent (minimisation)
 
void solve(State& s) {
    if (complete(s)) { best = min(best, cost(s)); return; }
    if (lowerBound(s) >= best) return;                  // PRUNE
    for (Choice c : orderedCandidates(s)) {
        apply(s, c);
        solve(s);
        undo(s, c);
    }
}

Three ingredients determine whether it works:

1. The bound — a fast, optimistic estimate of the best completion.
2. The incumbent — found early by a good heuristic, so pruning starts immediately.
3. The branching order — explore promising branches first.

The bound is everything

A bound must be admissible (never worse than the true optimum) and cheap. Stronger bounds prune more but cost more; the trade-off is the whole engineering problem.

Problem	Bound
TSP	sum of the two cheapest edges per city, halved
TSP (stronger)	MST of the unvisited cities + two connecting edges
TSP (strongest practical)	Held-Karp 1-tree Lagrangian bound
Knapsack	the fractional (LP) relaxation
Max clique	a greedy colouring of the candidate set
Scheduling / makespan	$\max (\text{average load},\text{longest job})$
Assignment	the Hungarian LP relaxation
Bin packing	$\lceil \text{total size}/\text{capacity}\rceil$
Graph colouring	max clique size
Any IP	the LP relaxation

The LP relaxation is the general answer — solve the fractional version and use its value as the bound. That is exactly what commercial MIP solvers do.

The colouring bound for max clique

Greedily colour the candidate vertices; a clique cannot be larger than the number of colours used. Cheap, and dramatically effective — it is why modern max-clique solvers handle graphs with hundreds of vertices.

Search order

Strategy	Memory	Note
Depth-first	$O(d)$	finds an incumbent quickly; the default
Best-first	$O(\text{tree})$	expands the most promising node; fewest nodes but memory-hungry
Breadth-first	huge	rarely used
Iterative deepening	$O(d)$	best-first behaviour with DFS memory
Depth-first with restarts	$O(d)$	escapes bad early choices

Depth-first is the practical default: it reaches a complete solution fast, which gives an incumbent, which enables pruning.

Getting a good incumbent early

Pruning only works once best is tight. So:

1. Run a greedy or heuristic first (LPT, nearest neighbour, local search) and seed best with its value.
2. Order the branches so the greedy choice is explored first.
3. Consider beam search on the first few levels to find a strong incumbent cheaply.

A good incumbent is often worth more than a better bound.

Branch and bound vs the alternatives

Situation	Method
Optimisation, good bound available	branch and bound
Feasibility (any solution)	backtracking
Small $n$, subset structure	bitmask DP
Splittable	meet in the middle
Exact cover structure	DLX
Integer linear program	branch and bound on the LP (branch and cut)
Approximate answer acceptable	heuristics

Branch and cut, branch and price

The industrial versions:

• Branch and cut — add violated cutting planes to tighten the LP relaxation before branching. This is how CPLEX and Gurobi solve TSP instances with tens of thousands of cities to proven optimality.
• Branch and price — generate variables (columns) lazily; used for vehicle routing and crew scheduling.

Not contest tools, but worth knowing that “NP-hard” does not mean “unsolvable in practice” — with good bounds, instances far beyond the exponential-DP range are routinely solved exactly.

Practical notes

• Prune before recursing, not after — checking the bound at the top of the call saves an entire subtree.
• Compute the bound incrementally where possible; a bound that costs $O(n)$ per node can dominate the runtime.
• Use $\ge$ rather than $>$ in the pruning test when you only need one optimal solution.
• Track the node count while debugging; if it is not dropping sharply as you add pruning, the bound is too weak.
• For contests, check the constraints first — if $n\le 22$ there is probably an intended bitmask DP, and branch and bound is unnecessary.

See also: Backtracking · Travelling Salesman · Approximation Algorithms