Branch-and-bound is the standard exact algorithm for Mixed-Integer Programming. It works by dividing the search space into subproblems (branching) and using continuous relaxations to prove that entire regions cannot contain the optimum (bounding and pruning). The three core operations are: Branch — split on a fractional variable, creating two child subproblems; Bound — solve the LP relaxation to get a lower bound (for minimisation); Prune — discard any subproblem where the lower bound is worse than the best integer solution found so far.
Termination is guaranteed because each branch fixes at least one variable, so the tree is finite. The depth and total nodes explored depend on how tightly the LP relaxation approximates the integer problem — a loose relaxation requires heavy branching, while a tight one often solves in a small tree.
Problem: Should we open warehouses in Cities A, B, C? Binary variables: y_A, y_B, y_C. Optimise opening costs + service costs.
LP relaxation: Allow binary variables to be continuous in [0,1]. Solution: y_A = 0.7, y_B = 0.4, y_C = 0.2, with objective value 45. This fractional solution is infeasible (you cannot "0.7 open" a warehouse) but gives a lower bound: the integer optimum is at least 45.
Branch on y_A: Create two subproblems: y_A = 0 (left) and y_A = 1 (right). Left child relaxes to y_A = 0, y_B = 0.6, y_C = 0.3, objective 48 — worse than 45, so likely not on the path to optimum. Right child relaxes to y_A = 1, y_B = 0.2, y_C = 0 integer!, objective 50. That is feasible — we have a candidate solution with cost 50.
Prune: Any branch with a lower bound ≥ 50 cannot improve on the current best. If the left child's deeper relaxations never drop below 50, we discard the entire left subtree.
Common confusion: "Branch-and-bound takes too long, so it's just a heuristic that finds approximate solutions."
Reality: Branch-and-bound is exact — it provably finds the optimum. The confusion arises because in practice, problems are large and time limits cut off exploration. When cut off, the solver returns the best integer solution found and a lower bound, proving a "gap" (e.g., "we found a solution with cost 100, and we know the optimum is between 98 and 100"). That gap is not approximation error — it is honest uncertainty. The algorithm, given unlimited time, will close the gap to zero and prove optimality.
Using branch-and-bound with a time limit is pragmatic engineering, but it does not make branch-and-bound a heuristic. It is like saying Dijkstra's algorithm is approximate because your GPS times out before reaching the destination.
Branch-and-bound speed depends on the integrality gap of the LP relaxation, not the solver. A tighter formulation always helps more than a faster machine.