Helpful context:

An airline has 200 planes and 5,000 possible routes. Each plane-route assignment has a fuel cost. Which assignment minimizes total fuel cost?

This is an integer programming problem - you can’t assign 0.7 of a plane to a route. Brute force is impossible: $5000^{200}$ possibilities. Continuous relaxation (pretend fractions are allowed) gives you a fast answer, but the answer might require half a plane on one route and 1.3 planes on another.

Branch and bound is how real airline scheduling software solves this. It’s also how Gurobi, CPLEX, and every major optimization solver works. It won’t change the worst-case complexity, but it typically finds the exact optimal solution dramatically faster than brute force - because it can prove that vast regions of the search space cannot contain the optimal answer without ever visiting them.

The Core Idea

Imagine the set of all possible solutions as a tree. The root is the unconstrained problem. Each internal node represents a partial decision - some variables have been fixed, others are free. Each leaf is a complete assignment.

Branch and bound navigates this tree with two operations:

Branching: Split a node into subproblems by restricting a variable to different values. If we’re assigning items to a knapsack, we might branch on whether item 3 is included or excluded. Each branch is a subtree.

Bounding: For each node, compute a bound on the best possible solution achievable anywhere in that node’s subtree. For minimization, compute a lower bound. For maximization, compute an upper bound.

Pruning: Maintain the best complete solution found so far (the incumbent). If a node’s bound is already worse than the incumbent, prune that subtree entirely - no solution there can beat what you already have.

The result: you systematically explore the solution space, but you never enter subtrees that can’t contain the optimal answer.

The Search Tree

A node in the B&B tree represents a partial solution: some variables fixed, others free. The root has no variables fixed. Leaves are complete assignments.

Best-first search: Use a priority queue ordered by bound. Always explore the node with the most promising bound first. This finds good solutions early and tightens the incumbent quickly, enabling more pruning. Requires $O(\text{tree size})$ memory.

Depth-first search with pruning: Dive deep to find a complete solution quickly, then backtrack and prune. Uses only $O(d)$ space where $d$ is the tree depth. Often faster in practice when good heuristics exist for finding the initial incumbent.

Here’s the basic algorithm for minimization:

BranchAndBound(problem):
    incumbent = +infinity
    pq = priority queue, insert root with lb = LowerBound(root)
    while pq not empty:
        node = ExtractMin(pq)           // best lower bound
        if node.lb >= incumbent: continue  // prune
        if node is a complete solution:
            incumbent = min(incumbent, node.value)
            continue
        for child in Branch(node):
            lb = LowerBound(child)
            if lb < incumbent:
                pq.insert(child, lb)
    return incumbent

Bounding: The Art of Tight Estimates

The power of B&B is entirely in the quality of the bound. A good bound must be:

  • Valid: A lower bound must genuinely be $\leq$ the true optimum of the subproblem. If you use an invalid bound, you might prune the optimal solution and return a wrong answer.
  • Tight: Close to the true optimum. A lower bound of 0 is always valid for non-negative costs, but it never prunes anything.
  • Fast to compute: You call the bounding function at every single node. If it takes 10 minutes to compute, you’d rather brute force.

Three common strategies:

LP relaxation: Relax integrality constraints - allow fractional solutions - and solve the resulting linear program. LP relaxations give tight bounds and can be solved in polynomial time. This is the workhorse of modern integer programming solvers.

Lagrangian relaxation: Move complicating constraints into the objective with a penalty. Easier to solve but gives weaker bounds.

Problem-specific combinatorial bounds: For TSP, a minimum spanning tree on remaining cities gives a lower bound on tour cost.

Traveling Salesman Problem

Given a complete weighted graph, find the shortest Hamiltonian cycle (visit every city exactly once and return to the start).

TSP is NP-complete. But B&B finds exact optimal solutions to instances with hundreds of cities in practice.

Branching strategy: At each node, pick an edge $e = (u, v)$ and branch on “include $e$ in the tour” vs “exclude $e$ from the tour.”

Lower bound via minimum spanning tree: A Hamiltonian cycle must visit every vertex, so it uses at least $n$ edges. A minimum spanning tree on the graph uses $n - 1$ edges and costs at most as much as the optimal tour (since removing one edge from the tour gives a spanning tree). So: MST cost is a valid lower bound on tour cost.

More precisely: for the subproblem where some edges are fixed, compute the MST of the remaining unconstrained graph and add it to the cost of the fixed edges. For a 10-city instance, this bound is typically within 5-15% of the optimal, which prunes the vast majority of branches.

0/1 Knapsack via Branch and Bound

Recall the 0/1 knapsack problem: $n$ items, each with weight $w_i$ and value $v_i$, knapsack capacity $W$. Maximize total value.

Branching: At each node, pick the next item $i$ and branch on $x_i = 1$ (include) vs $x_i = 0$ (exclude).

Upper bound via LP relaxation (fractional knapsack): Allow items to be fractionally included. Sort remaining items by value-to-weight ratio $v_i/w_i$ descending. Greedily fill the knapsack, possibly taking a fraction of the last item. This is the optimal fractional solution and can be computed in $O(n)$ after sorting once. Since the fractional solution is a relaxation of the integer problem, it gives a valid upper bound.

Example. Items $(v, w)$: $(10, 2), (6, 2), (12, 3), (15, 5)$, capacity $W = 7$.

Sorted by ratio: $(10,2)$ ratio 5, $(6,2)$ ratio 3, $(12,3)$ ratio 4, $(15,5)$ ratio 3.

Actually sorted: $(10,2)$, $(12,3)$, $(6,2)$, $(15,5)$ - ratios 5, 4, 3, 3.

LP relaxation at root: take items 1 and 2 (weight 5, value 22), then $\frac{2}{2}$ of item 3 (weight 2, value 6). Total value 28.0.

Branch on item 1. Left: $x_1 = 1$ (include). Right: $x_1 = 0$ (exclude).

Left child LP: items 1 included (weight 2, value 10), take item 2 (weight 3, value 12), then $\frac{2}{2}$ of item 3 (weight 2, value 6). Total 28.0.

Eventually the algorithm finds the true optimum: items 1, 2, 3 with value 28, weight 7 - exactly matching the LP bound, so that branch is confirmed optimal.

Discomfort check. Branch and bound still has exponential worst case - is it actually better than backtracking? Yes, because the bounds can prune exponentially many branches at once. Backtracking prunes only when a constraint is literally violated; B&B prunes when a bound shows the subtree can’t improve the incumbent, even if every individual constraint is satisfied. For problems with tight LP relaxations (like knapsack, where the LP optimum is often close to the integer optimum), B&B prunes almost everything. For loose relaxations, it prunes less. The art is finding tight bounds. Industrial solvers combine B&B with cutting planes - additional constraints that tighten the LP relaxation without cutting off any integer-feasible solution - and this combination (branch-and-cut) is why Gurobi can solve MILPs with millions of variables.

B&B vs. Other Approaches

Property Greedy Dynamic Programming Branch and Bound
Always finds optimal? Sometimes Yes (when applicable) Yes
Worst-case complexity Polynomial Polynomial Exponential
Practical speed Very fast Fast Often fast with good bounds
Requires optimal substructure? Problem-specific Yes No
Memory use $O(1)$ extra $O(\text{states})$ $O(\text{tree depth})$

DP and B&B both solve optimization problems exactly, but they’re suited to different problem structures. DP requires optimal substructure and works when the subproblem space is polynomial. B&B works for any discrete optimization problem, but its efficiency depends entirely on bound quality.

Summary

Component What it does Key requirement
Branching Split problem into subproblems Must cover all solutions
Bounding Compute best possible value in a subtree Must be valid (never wrong); tight (prunes well)
Pruning Discard subtrees worse than incumbent Requires good incumbent early
Best-first search Explore most promising nodes first Better pruning, more memory
LP relaxation Compute upper/lower bound via fractional problem Tight for many combinatorial problems

Branch and bound is the standard approach for exact optimization when DP doesn’t apply. It’s provably optimal - it always finds the global optimum - and in practice it exploits problem structure through tight bounds to navigate enormous search spaces efficiently. The worst case is still exponential, but real scheduling, routing, and resource allocation problems are solved to optimality every day by B&B solvers.

Read next: