Branch and Cut
Branch and cut combines branch-and-bound search with cutting planes that tighten the relaxation at each node, the core of modern MIP solvers.
Two ideas combined
Branch and cut fuses two techniques for integer programming. Branch and bound explores a tree of subproblems, pruning by bounds. Cutting planes add valid linear inequalities that remove fractional relaxation solutions without cutting off any integer-feasible point. Applying cuts at the nodes of the branch-and-bound tree, rather than only at the root, is what makes the combination powerful.
The node loop
At each node the solver solves the LP relaxation. If the solution is integer-feasible it updates the incumbent. If it is fractional, the solver first tries to generate cutting planes that separate the fractional point; adding them and re-solving may restore integrality or improve the bound. Only when cuts stop helping does the solver branch on a fractional variable, spawning child nodes.
- Gomory cuts: derived from the simplex tableau, generally applicable
- Cover and knapsack cuts: exploit combinatorial constraint structure
- Flow and clique cuts: specialized to network and packing structure
- Cut management: keep effective cuts, discard stale ones to control size
Why cuts at nodes help
A cut valid at the root is valid everywhere, but local cuts derived from a node's fixed variables can be even tighter for that subtree. Tighter relaxations mean better bounds, which means more pruning and fewer branches. In practice good cut generation can shrink a search tree from millions of nodes to a handful, turning an intractable model into a routine solve.
Engineering role
Branch and cut, plus presolve and primal heuristics, is the algorithm inside every serious mixed-integer solver. For an engineering program, it is the method that returns a provably optimal discrete-plus-continuous plan with a certified optimality gap, so a design or schedule can be defended as optimal, or within a known tolerance of optimal, rather than merely reasonable.