Branch and Bound

An integer program can have astronomically many candidate solutions — a problem with 100 yes/no decisions has 2^{100} of them, more than there are atoms in your body. You cannot check them one by one. Branch and bound is the clever search that solves such problems anyway, not by examining every candidate but by proving whole regions worthless without looking inside them. It is the engine inside every serious integer-programming solver.

The two ideas in the name

Bound. Drop the awkward "must be a whole number" requirement and solve the LP relaxation — a plain linear program, which is easy. Its optimum can only be better than the true integer optimum (we relaxed a constraint, so we can only do better), so for a maximisation it gives an upper bound on what any integer solution in this region could achieve.

Branch. If the relaxation happens to be all-integer, we're done — that region is solved. If some variable comes out fractional, say x_1 = 2.5, we split the region into two sub-problems that between them keep every integer point but exclude the fraction: x_1 \le 2 in one child, x_1 \ge 3 in the other. Recurse.

Pruning: the magic step

We keep the best integer solution found so far — the incumbent — as a lower bound. A whole branch can then be thrown away ("fathomed") without exploring it, for any of three reasons:

By bound — the node's relaxation is no better than the incumbent, so nothing inside it can beat what we already have.
By integrality — the relaxation is already all-integer; it's a candidate, so update the incumbent and stop.
By infeasibility — the sub-problem has no feasible solution at all.

Each prune can lop an exponential number of candidates off the search in one stroke. That is why branch and bound routinely solves problems with thousands of integer variables that brute force could never finish.

Watch it run

Here is the search tree for a small maximisation whose LP relaxation gives 22.5. Step through it and watch bounds prune branches away:

The left branch delivered an integer solution worth 21 — our incumbent. The right branch's best hope was only 20.5, and once we split it further, one child dropped to 19 (worse than 21, pruned by bound) and the other was infeasible (pruned). With every branch fathomed and nothing left to explore, the incumbent 21 is proven optimal — without ever enumerating all the candidates.

It is tempting to solve the easy LP relaxation and round the fractional answer to the nearest integers. Sometimes that works; often it is badly wrong. Rounding can land you outside the feasible region entirely, or at a feasible point far from the true integer optimum — for tightly-constrained problems the best integer solution can sit nowhere near the rounded LP solution. Branch and bound exists precisely because rounding is unreliable: it searches in a disciplined way that guarantees the optimum, rather than hoping a round-off happens to be good.

Branch and bound always works, but its speed swings by orders of magnitude with two choices: which variable to branch on and which node to explore next. Good bounds that prune early are worth everything — a weak relaxation prunes little and the tree explodes back toward brute force. Real solvers pour enormous effort into tightening bounds (cutting planes), finding good incumbents fast (heuristics), and clever branching rules. "Branch and bound" in practice is really "branch and cut and bound," and the difference is whether a problem solves in a second or a week.