Aspects of OR - Integer Programming (Part 3)

In Part 2 we saw how branch and bound systematically searches for integer solutions, using LP bounds to prune the search tree. The effectiveness of this approach depends critically on the quality of those bounds. Loose bounds mean less pruning, bigger trees, and slower solves.

Cutting planes address this directly: they add new constraints (cuts) to the LP relaxation that remove fractional solutions without eliminating any integer-feasible point. Each cut tightens the relaxation, improving the bound. In this post, we develop the geometric intuition behind cuts, derive Gomory cuts from the simplex tableau, and see how cover inequalities exploit knapsack structure. In Part 4, we combine cutting planes with branch and bound into branch-and-cut.

The geometric picture

To understand cutting planes, it helps to think in two dimensions. Consider the IP:

$\max \; 4x_1 + 5x_2 \quad \text{s.t.} \quad 3x_1 + 2x_2 \leq 12, \quad x_1 + 3x_2 \leq 9, \quad x_1, x_2 \geq 0, \; x_1, x_2 \in \mathbb{Z}.$

The LP relaxation has a polygonal feasible region (the LP polytope) with vertices at $(0, 0)$, $(4, 0)$, $(18/7, 15/7)$, and $(0, 3)$. The LP optimum sits at the vertex $(18/7, 15/7) \approx (2.57, 2.14)$ with value $21$.

Scattered inside this polytope are the integer-feasible points: $(0,0)$, $(1,0)$, $(2,0)$, $(3,0)$, $(4,0)$, $(0,1)$, $(1,1)$, $(2,1)$, $(3,1)$, $(0,2)$, $(1,2)$, $(2,2)$, and $(0,3)$. The IP optimum is $(2,2)$ with value $18$.

Picture this: the LP polytope is a quadrilateral, the LP optimum is its top-right vertex at $(2.57, 2.14)$, and the closest integer point in the optimal direction is $(2,2)$. There is a gap — the LP sees fractional territory that no integer point occupies.

A cutting plane is a line (hyperplane in higher dimensions) that slices off the fractional LP optimum while keeping all integer points on the feasible side. After adding the cut, the LP polytope shrinks — its new optimum is closer to the integer optimum, providing a tighter bound. We can repeat: add another cut, shrink the polytope further, resolve.

The ideal LP relaxation would be the convex hull of the integer points — the tightest possible convex set containing all integer-feasible solutions. If we could describe this convex hull explicitly, the LP relaxation would always return an integer solution. In general, the convex hull has exponentially many facets and cannot be written down. But we can iteratively add cuts that bring us closer to it.

Gomory cuts

The most classical cutting plane method is due to Ralph Gomory (1958). Gomory cuts are derived directly from the simplex tableau and can be applied to any IP — they do not exploit problem structure.

Derivation

Suppose we have solved the LP relaxation with the simplex method and the optimal solution has a fractional basic variable $x_i$ with value $\bar{b}_i \notin \mathbb{Z}$. The corresponding row of the simplex tableau is:

$x_i + \sum_{j \in N} \bar{a}_{ij} x_j = \bar{b}_i,$

where $N$ is the set of non-basic variables. Since all variables must be non-negative integers in the IP, we can derive the Gomory fractional cut:

$\sum_{j \in N} f_{ij} \, x_j \geq f_{i0},$

where $f_{ij} = \bar{a}_{ij} - \lfloor \bar{a}_{ij} \rfloor$ is the fractional part of $\bar{a}_{ij}$, and $f_{i0} = \bar{b}_i - \lfloor \bar{b}_i \rfloor$ is the fractional part of $\bar{b}_i$.

Why is this valid? Every integer solution satisfies the tableau row with integer values, so the fractional parts must "add up" correctly. The current LP solution violates the cut because all non-basic variables are zero, giving $0 \geq f_{i0}$ — a contradiction since $f_{i0} > 0$.

Worked example

Let us apply this to our 2D example. Adding slack variables $s_1, s_2 \geq 0$, the constraints become $3x_1 + 2x_2 + s_1 = 12$ and $x_1 + 3x_2 + s_2 = 9$.

Solving the LP and expressing the basic variables in terms of the non-basic ones ($s_1, s_2$, both zero at the optimum), the tableau row for $x_1$ is:

$x_1 + \tfrac{3}{7} s_1 - \tfrac{2}{7} s_2 = \tfrac{18}{7}.$

Since $x_1$ is fractional ($18/7 = 2 + 4/7$), we extract the fractional parts of each coefficient:

• $f_{i0} = \text{frac}(18/7) = 4/7$
• $f_{s_1} = \text{frac}(3/7) = 3/7$
• $f_{s_2} = \text{frac}(-2/7) = 5/7$ (since $-2/7 = -1 + 5/7$)

The Gomory cut is:

$\tfrac{3}{7} s_1 + \tfrac{5}{7} s_2 \geq \tfrac{4}{7}.$

At the current LP solution ($s_1 = s_2 = 0$), the left side is $0$, which violates $0 \geq 4/7$. The cut works.

To express this in the original variables, substitute $s_1 = 12 - 3x_1 - 2x_2$ and $s_2 = 9 - x_1 - 3x_2$, multiply through by 7, and simplify:

$2x_1 + 3x_2 \leq 11.$

Geometrically, this is a line that passes between the fractional LP optimum $(2.57, 2.14)$ and the integer points. The LP optimum violates it ($2 \times 2.57 + 3 \times 2.14 = 11.57 > 11$), but every integer-feasible point satisfies it (the worst case is $(2,2)$: $4 + 6 = 10 \leq 11$).

Adding this cut and resolving the LP gives a new optimum at $(2.8, 1.8)$ with value $20.2$ — tighter than the original bound of $21$. This new solution is still fractional, so we would generate another Gomory cut and repeat. After a few rounds, the LP solution converges to the IP optimum $(2,2)$ with value $18$.

Cover inequalities for knapsack

Generic cuts like Gomory cuts work for any IP but may be weak. For specific problem structures, we can derive much stronger cuts. Cover inequalities are a prime example, designed for knapsack constraints.

Consider a binary knapsack constraint:

$\sum_{j=1}^{n} w_j x_j \leq W, \quad x_j \in \{0, 1\}.$

A cover is a subset $C \subseteq \{1, \ldots, n\}$ of items whose total weight exceeds the capacity:

$\sum_{j \in C} w_j > W.$

Since the items in a cover cannot all be selected simultaneously, we get the cover inequality:

$\sum_{j \in C} x_j \leq |C| - 1.$

This is a valid inequality for the IP but may be violated by the LP relaxation — and that is exactly what makes it useful as a cut.

Example

Consider a 5-item knapsack with weights $(6, 7, 8, 9, 11)$, values $(12, 15, 17, 19, 22)$, and capacity $W = 25$.

The LP relaxation gives $x_1 = 0$, $x_2 = 1$, $x_3 = 1$, $x_4 = 1$, $x_5 = 1/11 \approx 0.09$, with LP value $53$. The IP optimum is items $\{2, 3, 4\}$ with value $51$.

Now consider the set $C = \{2, 3, 5\}$ with total weight $7 + 8 + 11 = 26 > 25$. This is a cover, so the cover inequality is:

$x_2 + x_3 + x_5 \leq 2.$

The current LP solution gives $x_2 + x_3 + x_5 = 1 + 1 + 1/11 \approx 2.09 > 2$, so this cut is violated. Adding it eliminates the current fractional solution and tightens the bound. Similarly, the covers $\{2, 4, 5\}$ and $\{3, 4, 5\}$ yield additional violated inequalities. Solvers generate and evaluate many such covers, adding only the most effective ones.

Extended cover inequalities strengthen the basic cover by also considering items outside the cover that are heavier than the lightest item in the cover, yielding even tighter cuts.

The pure cutting plane algorithm

Gomory proposed a clean iterative algorithm:

1. Solve the LP relaxation.
2. If the solution is integer, stop — it is optimal for the IP.
3. Otherwise, generate one or more cutting planes violated by the current LP solution.
4. Add the cuts to the LP and go to Step 1.

This algorithm is guaranteed to converge to the IP optimum in finite steps (for pure IPs). However, in practice it tends to be slow: it may require many rounds of cuts, and numerical issues accumulate as the LP grows with each added constraint.

The practical breakthrough came from combining cutting planes with branch and bound — a marriage of two complementary ideas. We cover this in Part 4.

Other families of cuts

Beyond Gomory cuts and cover inequalities, modern solvers use many specialized cut families:

• Clique inequalities — for constraints involving sets of mutually exclusive binary variables.
• Flow cover cuts — for network flow and fixed-charge structures.
• Mixed-integer rounding (MIR) cuts — a generalization of Gomory cuts that works well for mixed-integer programs.
• Lift-and-project cuts — derived by projecting higher-dimensional relaxations.

Each family exploits different structural features of the IP. A modern solver like Gurobi or CPLEX applies dozens of cut families automatically, selecting the most effective ones for the problem at hand.

Summary

Cutting planes tighten the LP relaxation by adding valid inequalities that remove fractional solutions while preserving all integer points. Gomory cuts work for any IP (derived from the simplex tableau), while cover inequalities exploit knapsack structure. The pure cutting plane algorithm converges in theory but is slow in practice. The real power comes from combining cuts with branch and bound — the subject of Part 4.