Branch-and-Cut: Integrating Cuts with Branching

Branch-and-cut is the workhorse algorithm of modern MIP solvers. At each node of a branch-and-bound tree, the solver tightens the LP relaxation with cutting planes before deciding whether to branch, prune, or stop. This lesson covers the node-level decision logic, the distinction between globally and locally valid cuts, how cuts can induce pruning, and how to read these events in a solver log.

Step 1 of 157%

Tutorial

The Branch-and-Cut Algorithm

The branch-and-cut algorithm interleaves cutting-plane generation with branch-and-bound. At every open node of the search tree, the solver alternates between strengthening the LP relaxation with cuts and splitting the feasible region by branching on a fractional variable.

The procedure at each node is:

Solve the LP relaxation. Let $z_{LP}$ be the optimal value and $\mathbf{x}^*$ the LP optimum.
Prune? Discard the node if any of these hold:
- By infeasibility: the LP has no feasible solution.
- By bound: the LP value cannot beat the incumbent $z^*$ . Prune when $z_{LP} \leq z^*$ (maximization) or $z_{LP} \geq z^*$ (minimization).
- By integrality: $\mathbf{x}^*$ is integer-feasible; update the incumbent if it improves on $z^*$ .
Cut. Otherwise, generate cutting planes (Gomory, MIR, cover, etc.) that are violated by $\mathbf{x}^*$ . Add the cuts to the LP and re-solve. Repeat for a bounded number of rounds.
Branch. If no further useful cuts are found and $\mathbf{x}^*$ is still fractional, pick a fractional variable $x_j$ and create two children with the bounds $x_j \leq \lfloor x_j^* \rfloor$ and $x_j \geq \lceil x_j^* \rceil$ .

Cuts can dramatically shrink the search tree by tightening bounds. Branching guarantees termination.