A general optimization technique that systematically explores a search space by branching into subproblems and using computed bounds on the best possible solution within each branch to prune regions that cannot contain an optimal solution.

Principle

Combine branching (decomposing the search space) with bounding (computing optimistic or pessimistic limits) and a search strategy to eliminate branches whose bounds show they cannot beat the current best solution.

Demonstration

Solving an integer linear program by branching on fractional variables: each node represents a subproblem with additional integrality constraints, and a relaxation (linear program) provides an upper bound; nodes whose relaxation bound is worse than the incumbent are pruned. In TSP, branch on subtour choices and use lower bounds to prune infeasible branches early.

Misapplication

Using weak or loose bounds, poor branching decisions, or an inappropriate node ordering that leads to little or no pruning, causing the algorithm to devolve into nearly exhaustive search and waste computation.

Consequence

If effective bounds and heuristics are available, the method can substantially reduce the explored space and guarantee optimality upon completion; it can also produce valid bounds and best-so-far solutions at intermediate times.

Reversal

Unpruned exhaustive enumeration (brute-force search) that examines all candidates without using bounds, or pure heuristic search that never guarantees optimality.

Boundary

Primarily suited to discrete and combinatorial optimization problems where bounds can be computed (e.g., integer programming, combinatorial scheduling). It is less directly applicable to problems without efficiently computable relaxations or to continuous problems without discretization/relaxation.

Semantic Tension

Tension between tightness of bounds and computational cost to compute them: tighter bounds prune more but may be expensive to obtain; contrasts with cutting-plane or heuristic methods that either improve bounds differently or sacrifice optimality for speed.

Synthesis

Branch and bound organizes a complete search by splitting the problem into subproblems and using bounds to discard unpromising regions; practical performance depends on the quality of bounds, branching rules, and node selection heuristics, yielding exact solutions when carried to completion and useful incumbents earlier.