Gomory Cutting Plane Method (Gomory Cuts): Fractional Cut Formula

Last updated: β€’ Sources β€’ Methodology

Gomory Cutting Plane Method (Gomory Cuts): Fractional Cut Formula + Worked Examples

The Gomory cutting plane method (also Gomory’s cutting-plane method) is a classic cutting plane method in integer programming. It adds Gomory cuts to an LP relaxation to eliminate fractional solutions while preserving all integer-feasible points.

Hands-on: use the Integer Linear Programming (ILP/MILP) calculator to compare branch-and-bound vs cut-based β€œbranch-and-cut (Gomory)”.

What you’ll learn here:
  • Gomory fractional cut formula and how to compute frac(Β·)
  • How a simplex tableau row turns into a cut
  • Why solver cuts can look like 9x5 + 11x6 + x7 β‰₯ 4
  • How Gomory cuts relate to LP relaxation bounds and the optimality gap (MIP)
On this page

Quick takeaway: Solve the LP relaxation, find a fractional basic integer variable in the simplex tableau, and add a valid inequality (a Gomory cut) that eliminates the current fractional optimum but keeps all integer-feasible solutions. This tightening improves bounds used by branch-and-bound, forming branch-and-cut.

What is the Gomory cutting plane method?

Definition

Conceptual definition (plain English)

The Gomory cutting plane method is an algorithm for integer linear programming (ILP) and mixed-integer linear programming (MILP) that:

  • solves an LP relaxation,
  • locates a fractional basic variable in the simplex tableau,
  • derives a cut that all integer-feasible solutions satisfy,
  • and repeats until integrality is reached or progress stalls.
Where it fits: Cuts tighten the relaxation bound (see LP relaxation bound) and can reduce the optimality gap (MIP).

Prerequisites (simplex, slack, infeasible/unbounded)

Prerequisites

Helpful pages in this cluster before you derive cuts

Gomory cuts are easiest when you are comfortable with simplex/tableau language and standard-form transformations.

If you’re new to integer optimization, start with ILP beginner’s guide and how to model ILP.

Gomory fractional cut formula (pure ILP)

Formula

The classic β€œGomory fractional cut” from a tableau row

In a pure ILP, choose a tableau row where an integer basic variable is fractional at the LP optimum. Write the row in the form: 

x_B = b - Ξ£_j a_j x_j

Define frac(t) = t - floor(t). The Gomory fractional cut formula is: 

Ξ£_j frac(a_j) x_j β‰₯ frac(b)

If you want the β€œwhy” behind the bound improvement, read LP relaxation bound and branch-and-bound.

How the algorithm works

Algorithm

Step-by-step (pure integer case)

  1. Solve the LP relaxation (simplex).
  2. Check integrality: if integer variables are all integers, stop.
  3. Pick a fractional tableau row for an integer basic variable.
  4. Compute fractional parts and add the cut.
  5. Re-solve the LP; repeat until integer-feasible or no useful cuts remain.

Practical solvers do this within branch-and-cut and manage numerical issues via settings like integrality tolerance.

Worked examples (1 open + solved examples collapsed)

Worked example (open)
Example 1 (pure ILP): derive a Gomory fractional cut and convert back to x-variables

Consider this pure integer linear program: 

maximize   z = x1 + x2
subject to  x1 + 2x2 ≀ 4
            3x1 +  x2 ≀ 5
            x1, x2 β‰₯ 0 and integer

Step 1 β€” Solve the LP relaxation

Relax integrality (allow x1, x2 to be continuous). At the intersection of the binding constraints: 

x1 + 2x2 = 4
3x1 + x2  = 5

Solving gives:

  • x2 = 7/5 = 1.4
  • x1 = 6/5 = 1.2

The LP optimum is fractional: (x1, x2) = (6/5, 7/5). (If you want to see why this bound matters, see LP relaxation bound.)

Step 2 β€” Put the LP in standard form (introduce slacks)

Add slack variables (see slack/surplus/artificial variables): 

x1 + 2x2 + s1 = 4
3x1 +  x2 + s2 = 5
x1, x2, s1, s2 β‰₯ 0

Step 3 β€” Express x1 and x2 in terms of slacks (tableau-style)

Solving the two equations for x1 and x2 in terms of s1, s2 gives: 

x1 = 6/5 + (1/5)s1 - (2/5)s2
x2 = 7/5 - (3/5)s1 + (1/5)s2

Step 4 β€” Choose a fractional integer basic variable row

Choose the x2 row because x2 = 7/5 is fractional but must be integer in the ILP: 

x2 = 7/5 - (3/5)s1 + (1/5)s2

Step 5 β€” Apply the Gomory fractional cut formula

Compute fractional parts (frac(t)=t-floor(t)):

  • frac(7/5)=2/5
  • frac(-3/5)=2/5
  • frac(1/5)=1/5

So the cut in slack space is:

(2/5) s1 + (1/5) s2 β‰₯ 2/5

Clear denominators (multiply by 5):

2 s1 + s2 β‰₯ 2

Step 6 β€” Convert the cut back to (x1, x2)

Use slack definitions:

s1 = 4 - x1 - 2x2
s2 = 5 - 3x1 - x2

Substitute into 2s1 + s2 β‰₯ 2:

2(4 - x1 - 2x2) + (5 - 3x1 - x2) β‰₯ 2
13 - 5x1 - 5x2 β‰₯ 2
x1 + x2 ≀ 11/5 = 2.2

Step 7 β€” Verify it cuts off the fractional LP optimum

At (x1, x2)=(1.2, 1.4), we have x1+x2=2.6, which violates x1+x2≀2.2. So this Gomory cut removes the fractional solution.

Where this goes next: In a full solve, you would re-optimize the LP with the new inequality and continue adding cuts (or branch). That combined strategy is branch-and-cut.
Solved example (collapsed)
Example 2: Why solver outputs show β€œ9×5 + 11×6 + x7 β‰₯ 4”

Searches like "9x5+11x6+x7>=4" gomory usually come from solver logs or notes. Two common reasons these look β€œodd”:

  1. Scaling / clearing denominators: solvers multiply a cut by a constant to remove decimals.
  2. Rewriting tableau variables: the cut may be derived in slack/tableau variables and then mapped back to original variables.

Concrete illustration (typical formatting)

Suppose the cut is computed as:

0.9 x5 + 1.1 x6 + 0.1 x7 β‰₯ 0.4

Multiply by 10:

9x5 + 11x6 + x7 β‰₯ 4
If your model’s LP relaxation is weak, see LP relaxation bound and how to model ILP for formulation strengthening.
Solved example (collapsed)
Example 3: Apply the fractional-part formula directly to a tableau row

Suppose an optimal tableau row for an integer basic variable is: 

xB = 3.4 - 2.3 x5 - 0.7 x6 - 1.2 x7

Fractional parts:

  • frac(3.4)=0.4
  • frac(2.3)=0.3
  • frac(0.7)=0.7
  • frac(1.2)=0.2

Gomory fractional cut:

0.3 x5 + 0.7 x6 + 0.2 x7 β‰₯ 0.4
If you’re getting confusing tableau cases, review multiple optimal solutions in LP and infeasible vs unbounded LP.
Solved example (collapsed)
Example 4: β€œWhat if my LP is solved with Excel/Python?” (workflow link example)

Many users learn cuts after solving LP relaxations in tools like Excel or Python:

For a cut derivation, you typically need tableau/basis information (not always exposed in spreadsheets), which is why solver-based branch-and-cut systems are the practical way cuts are used.

If you are using the CalcTypes calculator, exporting/importing your model may involve: What is Model JSON?

Pure ILP vs MILP (GMI cuts)

Variants

Pure ILP Gomory cuts vs Gomory mixed-integer cuts (GMI cuts)

Gomory’s classic fractional cuts are cleanest in pure ILP. In MILP settings, solvers use Gomory mixed-integer cuts (often called GMI cuts) along with many other cut families. See ILP vs MILP.

Setting Typical cuts Notes
Pure ILP (all integer) Gomory fractional cuts from tableau rows with fractional basic variables. Most common when people search β€œGomory fractional cut formula”.
MILP (mixed integer-continuous) GMI cuts + other solver cuts. Used inside branch-and-cut for robustness.

If you’re learning modeling, pair this with how to model ILP and ILP beginner’s guide.

Cuts vs branch-and-bound vs branch-and-cut

Comparison

Pros and cons at a glance

Method Pros Cons Typical use
Gomory-only (cutting plane) Elegant; can solve some small pure ILPs without branching. Numerically sensitive; may require many cuts. Teaching and small ILPs.
Branch-and-bound General; works for ILP/MILP. May explore many nodes if the relaxation is weak. Core MIP method.
Branch-and-cut Best practical performance; cuts tighten bounds and prune nodes. Harder to explain step-by-step. Modern solvers.

When Gomory cuts help

Guidance

When to rely on Gomory cuts (and what to do first)

  • Learning / intuition: perfect for seeing how a single inequality tightens an LP relaxation.
  • In practice: let solvers generate cuts; focus on stronger formulations and bounds.
  • Formulation support: use how to model ILP to tighten Big‑M, add bounds, and reduce symmetry.

Pitfalls (numerics, integrality tolerance)

Pitfalls

Mistake: expecting cuts to fix a weak model by themselves

Cuts help, but weak formulations (huge Big‑M values, missing bounds) can still perform poorly. Start with good modeling practice (see how to model ILP).

Pitfalls

Mistake: ignoring numerical stability

Gomory cuts come from tableau coefficients; poor scaling can create fragile cuts. This is why solvers use thresholds and parameters such as integrality tolerance.

If your LP behavior is confusing, verify whether it is infeasible or unbounded, or has multiple optima.

Questions people ask

Questions people ask

What is the main idea behind Gomory cutting planes?

Use the simplex tableau of the LP relaxation to create a valid inequality that eliminates the current fractional optimum but keeps all integer-feasible solutions.

Questions people ask

Are Gomory cuts still used in modern MIP solvers?

Yesβ€”typically inside branch-and-cut, together with other cuts. The goal is to tighten the LP relaxation bound and close the optimality gap faster.

Questions people ask

What does β€œGomory mixed integer cut” (GMI cut) mean?

It’s the mixed-integer extension used for MILP where some variables are continuous. Solvers generate these automatically while searching for an integer solution.

Questions people ask

Why does a Gomory cut sometimes look like β€œ9×5 + 11×6 + x7 β‰₯ 4”?

Solver logs often show scaled versions of cuts (to remove decimals) and cuts rewritten from slack/tableau variables (see slack variables).

Cluster learning path (internal links)

Internal linking

Recommended path (most relevant for Gomory cuts)

Follow this sequence to go from LP/tableau basics β†’ ILP/MILP β†’ bounds β†’ cuts.

Linear Programming (LP) Feasible region, simplex context, and LP terminology. Slack, Surplus & Artificial Variables Standard form and tableau-ready constraints. Two-Phase Simplex Method Tableau workflow used before deriving cuts. LP Relaxation Bound Why relaxations create bounds used in MIP. Branch-and-Bound (Integer Programming) Bounds, nodes, pruningβ€”where cuts help most. ILP/MILP Calculator Run branch-and-bound and small-model branch-and-cut (Gomory).
More LP + simplex toolkit pages (optional)
More ILP/MILP modeling + solver behavior pages (optional)
Implementations (Excel / Python) (optional)

What to do next

Next steps

Turn theory into intuition

  1. Build a small model using how to model ILP.
  2. Run it in the ILP/MILP calculator.
  3. Compare bound behavior using LP relaxation bound concepts.
  4. Interpret solver progress using the optimality gap.

Disclaimer

This Gomory cutting plane explanation and the associated calculator modes are provided for educational and informational purposes only. Cutting planes are numerically sensitive, and browser-based implementations are simplified compared to industrial solvers. Do not use this content or the calculator as the sole basis for high-stakes optimization decisions. Always validate models and results with a production-grade solver and a qualified operations research professional.

Sources
  1. Google OR-Tools β€” Mixed Integer Programming Documentation
  2. SCIP Documentation β€” Cutting Planes
  3. Wikipedia β€” Gomory’s Cutting-Plane Method
  4. Nemhauser & Wolsey β€” Integer and Combinatorial Optimization (MIT Press listing)