## Definition **Branch and Cut** combines [[Branch and Bound]] with **cutting plane methods**: at each node of the search tree, add valid inequalities (cuts) that tighten the LP relaxation before branching. The dominant algorithm framework in modern MILP solvers. ## The Idea Plain branch-and-bound branches when the LP relaxation gives a fractional solution. Branch-and-cut first tries to *cut off* the fractional solution by adding inequalities valid for the integer feasibility region but violated by the LP solution. If a cut tightens the LP enough to either prune the node or give an integer solution, no branching is needed. When cuts no longer help, fall back to branching. ## Cutting Planes A **cut** is an inequality satisfied by all integer-feasible points but not by the current LP-relaxation solution. Adding it tightens the LP relaxation toward the integer hull. ### Gomory Cuts The original cutting planes (1958). For any fractional variable in the LP solution, Gomory's procedure constructs a valid inequality that excludes the fractional point. Theoretically beautiful; numerically tricky in floating-point arithmetic — only recently became practical. ### Cover Cuts For knapsack-like constraints. If a set of items can't all fit, an inequality limiting how many fit becomes a cut. ### Clique Cuts For binary problems with conflict graphs (e.g., scheduling constraints). Add inequalities derived from cliques in the conflict graph. ### Lift-and-Project, Disjunctive Cuts More sophisticated cut families used in commercial solvers. ## The Algorithm ``` queue ← {original problem} while queue non-empty: P ← pop subproblem repeat: solve LP relaxation of P if infeasible or bound ≥ best: prune; break if solution is integer-feasible: update best; break find a cut violated by LP solution if cut found: add to P else: branch and push subproblems; break ``` ## Why It Works So Well - **Cuts tighten the relaxation.** Better bounds → more pruning → smaller search tree. - **Cut effort vs branching cost.** A few well-chosen cuts often outperform many branching steps. - **Sharing cuts across nodes.** Global cuts apply throughout the tree. ## Modern Solver Anatomy Commercial MILP solvers (Gurobi, CPLEX) deploy a dozen or more cut families, each with smart selection heuristics. Roughly: 1. **Preprocessing.** Simplify the problem before search. 2. **Heuristics.** Find initial feasible solutions for tight upper bound. 3. **LP relaxation + cutting planes at the root.** Tighten before any branching. 4. **Branch-and-cut.** Continue cutting at deeper nodes; branch when necessary. 5. **Parallel exploration.** Multiple threads search different subtrees. The result is solvers 100-1000x faster than 1990s-era implementations on the same problems. ## When Branch-and-Cut Shines - Integer programs with strong cutting-plane structure (TSP via subtour elimination cuts). - Problems where LP relaxation is close to IP optimum once tightened. - General-purpose MILP — almost always. ## Limits - **Cut selection is heuristic.** Adding bad cuts slows the LP without tightening usefully. - **Numerical conditioning.** Many cuts can ill-condition the LP basis. - **Memory.** Cuts accumulate; cut pools need management. ## Beyond Branch-and-Cut Modern solvers also feature: - **Conflict analysis** (borrowed from SAT solvers). - **Restarts** with learned globals. - **Symmetry breaking.** The MILP world has assimilated decades of algorithmic engineering. Branch-and-cut is the framework that ties it all together. ## Related - [[Branch and Bound]] - [[Integer Linear Programming]] - [[Linear Programming]]