Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 38 ยท Integer Programming

Cutting Planes and Formulation Strength

See why two correct integer models can solve very differently: LP relaxation strength, tight constraints, valid inequalities, cover cuts and Gomory cuts, with runnable examples.

Two integer models can describe exactly the same set of feasible integer solutions and still behave completely differently in a solver. One solves in a blink, the other runs for hours. The difference is the strength of the formulation: how closely its LP relaxation approximates the convex hull of the integer solutions. Better formulations give better bounds, and better bounds mean smaller branch-and-bound trees (Branch and Bound).

This lesson shows what a strong formulation looks like and how cutting planes (also called valid inequalities) strengthen a weak one.

The convex hull idea

Take the set of all feasible integer points. Its convex hull is the smallest convex polygon (polyhedron) containing them. If you could describe the hull with linear inequalities, the LP relaxation over the hull would have an integer optimum at a vertex, and an ordinary LP solver would solve the integer problem directly. For hard problems the hull needs far too many inequalities to write down, but we can add the most useful ones.

A formulation A is stronger than B if its relaxation is contained in B's (both are valid for the integers). Stronger means a tighter bound.

flowchart LR
    W["Weak formulation<br/>big feasible polygon"] --> S["Strong formulation<br/>smaller polygon"] --> H["Convex hull<br/>integer vertices only"]
    I["Integer points<br/>are the same in all three"] -.-> W
    I -.-> S
    I -.-> H

All three regions contain the same integer points; each step to the right removes fractional points and improves the LP bound.

Example: aggregated versus disaggregated linking

In facility location, a customer j may be served by facility i only if i is open. Let y_i be binary (open) and x_ij the fraction of customer j's demand served by i. Two correct ways to link them:

  • Weak (aggregated): sum_j x_ij <= C * y_i, where C is the number of customers.
  • Strong (disaggregated): x_ij <= y_i for every pair.

Both allow exactly the same integer solutions. But with the weak version, an LP can open a facility only to a fraction like y_i = 1/8 and still serve everyone from it, paying almost no fixed cost. Watch what that does to the relaxation bound.

Python Weak versus strong facility-location formulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The integer optimum is 155 in both models, but the weak relaxation only proves a bound of about 118, a 24% gap, while the strong relaxation proves 155 right away. The strong model is larger (32 linking rows instead of 4), yet it usually solves faster because the solver does not have to branch its way out of a poor bound. A bigger model is often a better model.

The same lesson applies to big-M constraints (Binary Variables and Logic): replacing x <= M*y with a smaller valid M, or with individual bounds like x_ij <= d_j * y_i, strengthens the relaxation.

Valid inequalities and cuts

A valid inequality is a constraint satisfied by every integer feasible point. A cutting plane is a valid inequality that the current fractional LP solution violates, so adding it removes that point from the relaxation without removing any integer solution. The loop is:

  1. Solve the LP relaxation.
  2. If the solution is integer, stop.
  3. Find a valid inequality it violates (separation). If none, stop and branch.
  4. Add the cut, go to 1.

Cover inequalities for knapsack constraints

For a constraint sum w_i x_i <= W with binary x, a cover is a set S of items whose weights add up to more than W. You cannot take all of them, so sum_{i in S} x_i <= |S| - 1 is valid. Cover cuts are generated automatically by every modern solver.

Python Cutting a knapsack relaxation with cover cuts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bound falls from 42.17 to 41.87 to 41.70 as three cuts are added, and then this simple search finds no more violated covers. The integer optimum is 41, so cover cuts closed about 40% of the gap here, and a real solver would add other cut families and branch to finish the job.

Gomory cuts

Cover cuts need special structure. Gomory fractional cuts work for any pure integer program. Take a row of the final simplex tableau whose basic variable has a fractional value:

TEXT
x_B + sum_j a_j x_j = b     with fractional part f0 = b - floor(b)

Let f_j = a_j - floor(a_j) be the fractional parts of the row coefficients. Then every integer solution satisfies:

TEXT
sum_j f_j x_j >= f0

where the sum is over the nonbasic variables. The current LP vertex has all nonbasic variables equal to 0, so it violates the cut (0 >= f0 > 0 is false). Add it, re-solve with the dual simplex method (the natural choice after adding a row), and repeat. Pure Gomory cutting converges in theory but can be numerically unstable, so solvers use them in moderation inside branch and cut.

Python One Gomory cut by hand on a tiny tableau row

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every integer point that makes x1 an integer satisfies the cut, but the fractional vertex does not, so the cut is both valid and useful.

How solvers use cuts

  • At the root they run several rounds of cuts (cover, Gomory, flow cover, mixed-integer rounding, clique) and keep the effective ones.
  • In the tree they add further cuts selectively; too many cuts slow every LP.
  • Presolve and bound tightening act before any LP: reduce coefficients, fix variables, tighten big-M.
  • Symmetry (identical machines or trucks) makes the tree large; adding ordering constraints such as y_1 >= y_2 >= y_3 breaks the symmetry.

Practical advice

  1. Prefer tight, disaggregated constraints when they are not too many.
  2. Compute the tightest valid big-M from the data.
  3. Compare LP relaxation values of alternative formulations; a bigger LP bound gap is a warning.
  4. Add problem-specific valid inequalities only when you know a reason they hold.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Two formulations have the same integer feasible points. What makes one stronger?

    Strength is about the relaxation: a smaller feasible region that still contains all integer points gives bounds closer to the integer optimum.
  2. 2. What must every cutting plane satisfy?

    A cut is valid if no integer feasible solution is removed. Being violated by the current fractional point is what makes it useful.
  3. 3. A knapsack constraint has items 2 and 3 with weights 20 and 35 and capacity 47. Which cover inequality is valid?

    The two weights add up to 55, more than 47, so they cannot both be chosen: the sum of the two binaries is at most 1.
  4. 4. In the Gomory cut, why is the current LP vertex cut off?

    At the vertex the nonbasic variables are zero, so the cut reads 0 >= f0 with f0 > 0, which is false.

Summary

  • Formulations with the same integer solutions can have very different LP bounds; stronger means a tighter relaxation.
  • Disaggregated linking constraints and tight big-M values strengthen models, even if they add rows.
  • Valid inequalities (cuts) remove fractional points; cover cuts suit knapsack rows, Gomory cuts apply to any pure integer program.
  • Solvers combine presolve, cut rounds and branching; you help them with strong formulations.

Next: Network Flow Models