Cutting Planes: Concept and Loop

When we drop the integrality requirement from an integer program (IP), we obtain its LP relaxation. The LP relaxation is easier to solve, but its optimum $\mathbf{x}^*$ is typically fractional and therefore infeasible for the IP.

A cutting plane (or cut) for an IP at the point $\mathbf{x}^*$ is a valid inequality

$$\boldsymbol{\alpha}^\top \mathbf{x} \le \beta$$

that is violated by $\mathbf{x}^*$. Two conditions must hold:

1. Validity: every integer-feasible point of the IP satisfies $\boldsymbol{\alpha}^\top \mathbf{x} \le \beta$.
2. Violation: $\boldsymbol{\alpha}^\top \mathbf{x}^* > \beta$.

Geometrically, adding the cut to the LP removes the fractional point $\mathbf{x}^*$ from the feasible region while keeping every integer-feasible point.

For example, suppose an IP has integer-feasible set $S = \{(0,0),\,(1,0),\,(0,1)\}$ and LP relaxation optimum $\mathbf{x}^* = (0.7,\,0.7)$. Consider the inequality $x_1 + x_2 \le 1$:

• Validity: at the points of $S$, $x_1 + x_2$ equals $0,\,1,\,1$, all $\le 1$. $\checkmark$
• Violation: at $\mathbf{x}^*$, $0.7 + 0.7 = 1.4 > 1$. $\checkmark$

Both conditions hold, so $x_1 + x_2 \le 1$ is a cutting plane.