Branch and bound

Branch and bound is the systematic pessimist's approach to constraint optimization. It explores the search tree of possible assignments like backtracking, but at each node it computes a bound on the best solution that could possibly be found in the subtree below. If that bound is worse than the best solution already found, the entire subtree is discarded — not because it contains no solution, but because it contains no solution worth finding.

The method requires two ingredients: a branching rule that divides the problem into subproblems, and a bounding rule that estimates the best achievable value in each subproblem. The tighter the bound, the more of the search space is pruned. The most powerful modern solvers combine branch and bound with constraint propagation, linear programming relaxations, and cutting planes — creating a hybrid that prunes by infeasibility, by suboptimality, and by learned structure.

Branch and bound is not a discovery algorithm. It is a discarding algorithm. Its power comes not from what it finds but from what it refuses to look at. In this it resembles scientific reasoning itself: the progress of knowledge is less a march toward truth than a retreat from demonstrable falsehood. The bound is the formalization of "not worth my time" — and in a universe of exponential possibilities, that formalization is survival.