Cutting Planes and Branch-and-Cut

Idea: "Cutting off" fractional vertices

LP relaxation may yield fractional optima (x₁ = 1.5, x₂ = 0.7...). Is it possible to add "smart" linear constraints that "cut off" these fractional solutions without removing any integer ones? This is precisely what cutting planes do. Instead of branching immediately, we add such planes to "pull" the LP optimum towards integer points. The combination of cutting planes and B&B constitutes Branch-and-Cut—the standard of modern MILP solvers.

What is a cutting plane?

Definition: an inequality $a^\top x \leq b$ is called a cutting plane for MILP if:

1. It holds for all integer feasible points $x \in {0,1}^n$
2. It is violated by the current LP optimum $x^*$ (fractional)

By adding such an inequality, we "cut off" the fractional $x^*$, but do not lose any integer solution. The new LP relaxation gives a better (higher) lower bound.

Gomory Cuts

Ralph Gomory's idea (1958): take a row of the simplex tableau for a fractional variable and generate a cutting plane.

Procedure: Suppose $x_i = a_0 + \sum_j a_j s_j$ (simplex tableau row, $s_j$ are non-basic variables). Write $x_i = \lfloor a_0 \rfloor + f_0 + \sum_j (\lfloor a_j \rfloor + f_j) s_j$, where $f_j = a_j - \lfloor a_j \rfloor \in [0,1)$.

Since $x_i$ is integer: $\sum_j f_j s_j - f_0 \in \mathbb{Z}$. Since $s_j \geq 0$: $\sum_j f_j s_j \geq f_0 > 0$.

Gomory Cut: $\sum_j f_j s_j \geq f_0$. This is violated for the current solution ($s_j = 0 \rightarrow 0 \geq f_0 > 0$), but holds for integer ones.

Gomory Theorem: In a finite number of iterations, using Gomory cuts, any bounded MILP is solved optimally.

Cuts for TSP: Subtour Inequalities

TSP is a "test ground" for cutting planes. Key cuts:

Subtour exclusion inequalities: For any subset of cities $S \subsetneq V$, $|S|\geq 2$:

$ \sum_{(i,j) \in E,, i \in S,, j \in S} x_{ij} \leq |S| - 1 $

Meaning: In a subset $S$ of $k$ cities, there cannot be $k$ or more route edges (otherwise, a closed subtour forms).

Number of such inequalities: $2^n$—exponential! We do not add them all at once. Instead: separation problem—for a given fractional $x^*$, find a violated inequality. For subtours—minimal cut in the network in $O(n^2)$.

Comb inequalities (stronger): cuts of the "handle + teeth" type. Theoretically better, practically harder to generate.

Branch-and-Cut: Algorithm

1. Root node: solve LP relaxation
2. Cutting plane loop: While there are violated cutting planes:
   • Find a violated inequality (separation problem)
   • Add it to the LP
   • Resolve the LP
3. If the solution is integer → update incumbent, prune
4. If fractional → branch (B&B)
5. In each node of the tree, again apply steps 2–3

Why is this more powerful than pure B&B: Cutting planes "pull" the LP bounds toward integer ones, making pruning more aggressive. Fewer nodes need to be examined.

Types of Cuts in Modern Solvers

Gurobi/CPLEX automatically generate different types of cuts:

• Gomory cuts: general for any MILP
• Cover cuts: specifically for knapsack problems (cover inequalities)
• Clique cuts: for problems with clique constraints
• Flow cuts: for problems with network structure
• MIR cuts (Mixed Integer Rounding): generalization of Gomory

Full Analysis: Subtour Cuts for TSP

Data: 4 cities, distance matrix $d = [[0,2,9,10],[1,0,6,4],[15,7,0,8],[6,3,12,0]]$.

LP optimum (without cuts): fractional solution, for example $x_{12} = x_{21} = 0.5$, $x_{34} = x_{43} = 0.5$, $x_{13} = x_{14} = 0.5$ — a "double" subtour.

Violated subtour inequality: For $S = {1,2}: x_{12} + x_{21} \leq 1$. Current value: $0.5 + 0.5 = 1$. Not strictly violated—look for another.

For $S = {3,4}: x_{34} + x_{43} \leq 1$. Also = 1. Add both constraints.

After adding: LP is resolved, fractional parts decrease. After several iterations, the LP optimum becomes integer, or B&B completes the task.

Types of Cutting Planes

Besides the classical Gomory cuts based on the simplex tableau, Branch-and-Cut applies:

• MIR cuts (Mixed Integer Rounding): Gomory generalization for mixed problems
• Cover cuts: for knapsack problems—if a subset of items exceeds $W$, not all its elements can be taken
• Clique cuts: for the conflict graph of variables—if in clique $K$ at most one variable can be 1, add $\sum x_i \leq 1$
• Flow cover cuts: for network problems
• Lift-and-project cuts (Balas, Ceresa, Cornuéjols): strong cuts from 0-1 constraints

Branch-and-Cut Workflow

A modern solver combines branching with aggressive cut generation:

1. At each node, solve LP relaxation
2. If the solution is not integer—try to add cuts to strengthen the bound
3. If cuts help—continue adding them (cut loop)
4. If cuts stop improving—branch

This approach, together with heuristics, has turned MILP from a "theoretically interesting" into a practically solvable problem—over 25 years (1990–2015), solver speed increased by a factor of a million.

Applications

Branch-and-Cut solves the world's largest routing problems (TSP up to 85,900 cities solved exactly—Pla85900), nuclear plant shift scheduling (EDF, France), gas supply optimization (E.ON).