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 the LP 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 LP relaxation, improving the bound. The combination of cutting planes with branch and bound is called branch-and-cut, and it is the algorithmic engine behind every modern IP solver.

The cutting plane idea

Consider an IP with feasible region $S = \{x \in \mathbb{Z}^n : Ax \leq b, \; x \geq 0\}$ and its LP relaxation with feasible region $P = \{x \in \mathbb{R}^n : Ax \leq b, \; x \geq 0\}$. Clearly $S \subseteq P$.

A valid inequality (or cut) for $S$ is an inequality $\alpha^T x \leq \beta$ that is satisfied by every point in $S$ but violated by some points in $P$ — in particular, by the current fractional LP solution. Adding this cut to the LP shrinks $P$ without losing any integer points.

The ideal LP relaxation would be the convex hull of $S$: the smallest convex set containing all integer-feasible points. If we could describe this convex hull explicitly, the LP relaxation would always give integer solutions. 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.

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$.

This inequality is valid for all integer solutions but violated by the current LP solution (where all non-basic variables are zero, giving $0 \geq f_{i0}$, a contradiction since $f_{i0} > 0$).

Example

Consider a small IP:

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

The LP relaxation gives $x_1 = 3, x_2 = 2$ with value 22. This is already integer! In this case no cuts are needed.

Let us modify the problem slightly to create a fractional LP solution:

$\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 optimal solution is $x_1 = 18/7 \approx 2.57$, $x_2 = 15/7 \approx 2.14$, with LP value $\approx 21.14$.

From the simplex tableau row for $x_1$, we can derive a Gomory cut. The fractional parts give us an inequality like $x_1 + x_2 \leq 4$ (the exact form depends on the tableau). Adding this cut to the LP and resolving tightens the bound. After one or two rounds, the LP solution becomes integer.

Cover inequalities for knapsack

For specific problem structures, we can derive much stronger cuts than generic Gomory 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.

Example

Using the knapsack from Parts 1 and 2: weights $(10, 20, 30)$, capacity 50.

The set $C = \{2, 3\}$ with total weight $20 + 30 = 50$ is not a cover (we need strictly greater). But $C = \{1, 2, 3\}$ with total weight $10 + 20 + 30 = 60 > 50$ is a cover. The cover inequality is:

$x_1 + x_2 + x_3 \leq 2.$

This is automatically satisfied here (we can take at most 2 items anyway), so it does not cut off the LP solution. In larger knapsack instances with many items, cover inequalities can be highly effective at tightening the LP relaxation.

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 the following 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, pure cutting plane algorithms tend to be slow in practice: they may require many rounds of cuts, and numerical issues accumulate as the LP grows.

Branch-and-cut

The practical breakthrough came from combining cutting planes with branch and bound into branch-and-cut:

1. At each node of the B&B tree, solve the LP relaxation.
2. Before branching, try to generate cutting planes that are violated by the current LP solution.
3. If effective cuts are found, add them to the LP and resolve. Repeat until no more useful cuts can be found.
4. If the LP solution is still fractional, branch as in standard B&B.

This approach gets the best of both worlds: cuts tighten the LP bounds (leading to more pruning), and branching handles the remaining integrality gap.

Modern solvers implement this with sophisticated cut management:

• Cut generation at each node using multiple families of cuts (Gomory, cover, clique, flow cover, mixed-integer rounding, and many more).
• Cut selection to choose the most effective cuts and avoid adding too many (which would slow down the LP solves).
• Cut aging and removal of cuts that are no longer binding.

What modern solvers actually do

A solver like Gurobi or CPLEX performs dozens of operations beyond basic branch-and-cut. Here is a simplified overview of the solve process:

Presolve: Before any LP is solved, the solver simplifies the model. This includes fixing variables whose values are determined by the constraints, tightening variable bounds, removing redundant constraints, detecting infeasibility early, and reformulating parts of the model. Presolve alone can reduce a problem by 50% or more.

Root node processing: At the root node, the solver invests heavily in cutting planes. It generates multiple rounds of cuts from various families, keeping only the most effective ones. It also runs primal heuristics to find good feasible solutions quickly — these serve as the initial incumbent for pruning.

Tree search: The solver then explores the B&B tree, generating cuts at some (not all) nodes, running heuristics periodically, and using adaptive node and variable selection strategies. It monitors the MIP gap and adjusts its strategy dynamically.

Parallelism: Modern solvers exploit multiple CPU cores by exploring different subtrees in parallel (deterministic or opportunistic parallelism).

Seeing it in action with Gurobi

Gurobi logs provide insight into the branch-and-cut process. Let us solve a slightly larger knapsack to see cuts in action:

import gurobipy as gp
from gurobipy import GRB
import random

random.seed(42)

n = 20  # 20 items
weights = [random.randint(5, 50) for _ in range(n)]
values = [random.randint(10, 100) for _ in range(n)]
capacity = int(0.4 * sum(weights))

model = gp.Model('knapsack_20')
model.Params.OutputFlag = 1  # show solver log

x = model.addVars(n, vtype=GRB.BINARY, name='x')

model.setObjective(gp.quicksum(values[j] * x[j] for j in range(n)), GRB.MAXIMIZE)
model.addConstr(gp.quicksum(weights[j] * x[j] for j in range(n)) <= capacity, 'capacity')

model.optimize()

selected = [j for j in range(n) if x[j].X > 0.5]
print(f'\nSelected items: {selected}')
print(f'Total weight: {sum(weights[j] for j in selected)} / {capacity}')
print(f'Total value: {model.ObjVal:.0f}')

In the solver log, you will see lines like:

Cutting planes:
  Cover: 3
  GUB cover: 1

This shows that Gurobi added cover inequalities (and GUB cover inequalities, a generalization) to tighten the LP relaxation at the root node. For this small problem, the cuts combined with presolve may be sufficient to close the gap entirely at the root, requiring zero or very few branch-and-bound nodes.

Accessing cut information

Gurobi also allows you to add your own cuts via lazy constraints or user cuts. This is useful when you know problem-specific valid inequalities:

import gurobipy as gp
from gurobipy import GRB

def my_callback(model, where):
    if where == GRB.Callback.MIPNODE:
        status = model.cbGet(GRB.Callback.MIPNODE_STATUS)
        if status == GRB.OPTIMAL:
            x_val = model.cbGetNodeRel(x)
            # Check for violated cuts and add them
            # model.cbCut(expr <= rhs)

model = gp.Model('with_cuts')
# ... define variables and constraints ...
model.optimize(my_callback)

This callback mechanism is used in practice for problems like the TSP, where subtour elimination constraints are added on-the-fly as they become violated (there are exponentially many, so adding them all upfront is impractical).

Performance impact

To illustrate the impact of cuts, consider solving an IP in three modes:

1. LP relaxation only — solve the LP, report the bound. Fast but loose.
2. Branch and bound only — disable cuts in the solver. The tree may be very large.
3. Branch-and-cut — the default. Cuts tighten bounds, leading to smaller trees.

import gurobipy as gp
from gurobipy import GRB

# ... define model as above ...

# Mode 2: B&B only (disable cuts)
model.Params.Cuts = 0
model.optimize()
print(f'Nodes explored (no cuts): {model.NodeCount}')

model.reset()

# Mode 3: Branch-and-cut (default)
model.Params.Cuts = -1  # automatic (default)
model.optimize()
print(f'Nodes explored (with cuts): {model.NodeCount}')

For many problems, enabling cuts reduces the number of B&B nodes by an order of magnitude or more.

Summary of the IP mini-series

Across the three parts, we covered:

1. Part 1 — IP definitions, LP relaxation, why rounding fails, knapsack and facility location examples.
2. Part 2 — Branch and bound: the tree search algorithm, pruning criteria, node and variable selection, worked knapsack example.
3. Part 3 — Cutting planes (Gomory cuts, cover inequalities), branch-and-cut, and how modern solvers work.

Together with the LP mini-series, these six posts cover the core theory and algorithms of mathematical programming. This foundation supports everything that follows in the Aspects of OR series — from scheduling to vehicle routing to network design.