Cutting Planes

Interactive visualizations for Chapter 6 of the Ricerca Operativa notes

The ILP

We work with the following Integer Linear Program:

\[ \begin{aligned} & \text{maximize} && 5\,x_1 + 4\,x_2 \\ & \text{subject to} && 3\,x_1 + 2\,x_2 \leq 14 \\ & && x_1 + 4\,x_2 \leq 12 \\ & && x_1, x_2 \geq 0, \quad x_1, x_2 \in \mathbb{Z}. \end{aligned} \]

Because both variables must be integers, the feasible set is no longer a convex polytope but a discrete lattice of points. The cutting-plane method (Gomory, 1958) bridges this gap: solve the LP relaxation, identify a fractional variable, derive a valid inequality (a cut) that eliminates the fractional optimum without removing any integer-feasible point, and repeat until integrality is achieved.

Step 1: LP Relaxation

Drop the integrality constraints and solve the resulting LP. The feasible region becomes the convex polygon defined by \(3x_1 + 2x_2 \leq 14\), \(x_1 + 4x_2 \leq 12\), \(x_1, x_2 \geq 0\).

The LP optimum is at \((x_1, x_2) = (3.2,\, 2.2)\) with \(z_\text{LP} = 24.8\).

The gray dots are the integer lattice points inside the LP feasible region. The LP optimum (orange star) at \((3.2, 2.0)\) is not a lattice point: \(x_1 = 3.2\) is fractional. This means the LP relaxation overestimates the true integer optimum.

Key observation: \(z_\text{LP} = 5(3.2) + 4(2.2) = 16 + 8.8 = 24.8\). Since the objective coefficients and variables must be integers, the objective value for any integer feasible solution must be an integer. Thus, we know the true integer optimum satisfies \(z_\text{ILP} \leq \lfloor 24.8 \rfloor = 24\).

Step 2: Identifying the Fractional Variable

At the LP optimum, both \(x_1 = 3.2\) and \(x_2 = 2.2\) are fractional. We select \(x_1\) as the source row for the Gomory cut.

The row for the basic variable \(x_1\) reads:

\[ x_1 + \tfrac{2}{5}\,s_1 - \tfrac{1}{5}\,s_2 = \tfrac{16}{5} \]

where \(s_1, s_2 \geq 0\) are the slack variables for constraints 1 and 2. Since \(x_1 = 16/5 = 3.2\) is not integer, we derive a Gomory fractional cut from this row.

Step 3: Deriving the Gomory Cut

The Gomory cut procedure extracts the fractional parts of all coefficients in the chosen row and turns them into a new valid inequality.

Why is the cut valid? The inequality \(2x_1 + 4x_2 \leq 15\) is satisfied by every integer point in the original LP region (you can verify: all lattice points above satisfy it). It only cuts off the fractional extreme point \((3.2, 2.2)\) and the red shaded area around it.

Step 4: Integer Optimum

With the Gomory cut in force, the LP relaxation is re-solved over the tightened region. The new LP optimum coincides with an integer point.

After adding the cut \(2x_1 + 4x_2 \leq 15\), the LP optimum of the tightened problem falls on the integer point \((4, 1)\).

Point \(z = 5x_1 + 4x_2\) Feasible ILP?
\((3, 2)\) \(15 + 8 = 23\) Yes
(4, 1) \(20 + 4 = \mathbf{24}\) Yes — optimal!
\((3.2, 2.2)\) \(16 + 8.8 = 24.8\) No (fractional)

Interesting fact: \(z_\text{LP} = 24.8\) and \(z_\text{ILP} = 24\). The LP optimum was fractional and needed to be cut off to find the integer solution.

Convergence Concept

The Gomory method is an iterative refinement procedure. Each cut tightens the LP relaxation by removing a fractional extreme point. After a finite number of cuts, the LP optimum must be integer.

How the algorithm terminates:

  1. Iteration 0 — Solve LP relaxation. Optimum is \((3.2, 2.0)\): fractional in \(x_1\).
  2. Iteration 1 — Add Gomory cut \(2x_1 + 4x_2 \leq 15\). Re-solve LP. The old fractional extreme point is cut off; the new LP optimum may still be fractional.
  3. Iteration 2+ — Add further cuts. The LP feasible region shrinks toward the integer hull (the convex hull of all integer-feasible points).
  4. Termination — When the LP optimum is integer, it is optimal for the ILP.

Theoretical guarantee: Gomory (1958) proved that this process terminates in a finite number of iterations for any ILP with rational data. In practice, the method is combined with branch-and-bound to handle large problems efficiently.