Branch-and-Cut

Branch-and-cut is the exact mixed-integer programming (MIP) solution framework underlying every modern commercial and open-source MIP solver. It combines two ideas: (a) **branch-and-bound** — divide the integer problem into smaller sub-problems via variable branching, solve the LP relaxation at each node and prune sub-trees whose LP bound is worse than the current best feasible solution; (b) **cutting planes** — before branching, add valid inequalities (cuts) that are satisfied by every integer feasible solution but cut off the current fractional LP optimum, tightening the relaxation and shrinking the bound gap. The approach was pioneered by Dantzig, Fulkerson and Johnson (1954) on the Travelling Salesman Problem (TSP) — they used subtour-elimination cuts inside a branch-and-bound search and solved a 49-city instance to optimum. Padberg and Rinaldi (1991) generalised the framework with separation routines that detect violated cuts on the fly. Today branch-and-cut is the default exact method for TSP, VRP, scheduling, facility location and dozens of other combinatorial-optimisation problems; reported solver performance on TSP has crossed 85K+ nodes (Applegate, Bixby, Chvátal and Cook 2006). Cuts used in practice: subtour-elimination, comb inequalities, clique cuts, Gomory cuts, mixed-integer-rounding cuts, lift-and-project cuts.