Branch and Bound

Branch and bound (B&B) is the standard exact solution method for mixed-integer programming (MIP) and many discrete optimization problems. It was introduced by Land and Doig (1960) for MIP, applied to TSP by Little et al. (1963), and clarified for integer constraints with the Dakin (1965) branching rule. The algorithm partitions the feasible region recursively into subregions (branching — e.g. for integer variable x with fractional x*, create two children x ≤ ⌊x*⌋ and x ≥ ⌈x*⌉), solves an **LP relaxation** at each node to obtain a lower bound (for minimization), tracks an upper bound via the best integer-feasible solution found (incumbent), **prunes by bound** any node whose LP bound is no better than the incumbent, **prunes by integrality** when the LP solution is already integer, and discards infeasible nodes. When the tree is exhausted the incumbent is the global optimum. Branch-and-cut (Padberg and Rinaldi 1991) couples B&B with cutting planes and is the backbone of modern MIP solvers. Branch-and-price (Barnhart et al. 1998) couples it with column generation and solves enormous formulations. Branching strategy (most-fractional, strong branching, pseudocost branching), node selection (best-first, depth-first, best-estimate) and presolving dramatically affect B&B performance. Wolsey (1998) *Integer Programming* and Nemhauser and Wolsey (1988) are standard references. Modern MIP solvers handle 100M-variable problems via the combination of B&B + cuts + heuristics.