Take a row of the final tableau whose basic variable is fractional and split every coefficient into its floor and its fractional part. The fractional parts give an inequality that every whole-number plan satisfies and the current relaxation optimum breaks, so it can be added; the dual simplex restores optimality; and repeating drives the corner toward a whole point without ever removing one.
Core ideas
One hard idea, and it is what the word “valid” covers: a claim about every whole-number plan, not about the fractional point you would like to remove.
Write each coefficient as its floor plus a fractional part in [0, 1). Move the floors to the other side; what remains is Σ f_j x_j ≥ f_0, an inequality built out of the parts that could not be accounted for by whole multiples. It is a consequence of the row together with integrality, so no whole-number plan breaks it.
A cut is valid when no whole-number plan in the region violates it. Cutting off the current fractional corner is what makes a cut useful and has nothing to do with whether it is valid. x₁ + x₂ ≤ 4 removes the corner on this instance and also removes (3, 2), (4, 1) and (5, 0) — which are the three optimal plans.
The added row makes the current tableau infeasible and leaves it optimal, which is the dual simplex's case exactly — the same fact that let a branch-and-bound child start from its parent. Each cut here costs one pivot, and two cuts take this instance from a fractional corner to a whole one.
The material
The derivation, the validity claim, the re-solve, and the inequality that looks like a cut and is not one.
Take max x₁ + x₂ subject to 2x₁ + 5x₂ ≤ 16 kiln hours and 6x₁ + 5x₂ ≤ 30 glaze. The relaxation stops where the two rows meet, at (7/2, 9/5), worth 53/10. Sixteen whole points lie in the region, around the region, and the best of them is worth 5 — attained at (3, 2), at (4, 1) and at (5, 0), three ways.
For a rational a, the floor ⌊a⌋ is the largest integer at most a and the fractional part is f = a − ⌊a⌋, which lies in [0, 1). On a fraction n/d this is a division with remainder, so nothing is rounded and f is exact: ⌊9/5⌋ = 1 and the fractional part is 4/5.
Let a row of the final tableau read Σ a_j x_j = b with the basic variable fractional, and let f_j and f₀ be the fractional parts of a_j and b. Then Σ f_j x_j ≥ f₀ is a Gomory cut: it is satisfied by every non-negative integer solution of the row and violated by the current relaxation optimum.
Every non-negative integer point satisfying the original rows satisfies Σ f_j x_j ≥ f₀.
Substitute a_j = ⌊a_j⌋ + f_j and b = ⌊b⌋ + f₀ into the row and rearrange: Σ f_j x_j − f₀ = ⌊b⌋ − Σ ⌊a_j⌋ x_j.
For integer x the right-hand side is an integer, so the left-hand side is an integer too. And f₀ is in [0, 1) while every f_j and every x_j is non-negative, so Σ f_j x_j − f₀ is greater than −1. An integer greater than −1 is at least 0, which is the cut.
□
The derivation used integrality twice and the objective not at all, which is why the cut is a fact about the feasible set rather than about the problem being solved. It is also why it is safe to add: the region shrinks, every whole point stays, so z_IP cannot move while z_LP can only fall.
The row whose basic variable is x₂ gives, in the tableau's own variables, (3/10)s₁ + (9/10)s₂ ≥ 4/5, where s₁ and s₂ are the slacks of the kiln and glaze rows. Substituting the slacks back turns that into 6x₁ + 6x₂ ≤ 31 in the reader's own coordinates. At (7/2, 9/5) the left-hand side is 6(7/2) + 6(9/5) = 21 + 54/5 = 159/5, which is 31.8 and breaks it. At every whole point of the region it holds, because 6x₁ + 6x₂ is a multiple of 6, so breaking ≤ 31 would need 36, which means x₁ + x₂ ≥ 6 — and the relaxation's own optimum is 53/10, so nothing in the region gets near it.
Add that cut and re-solve. One dual-simplex pivot moves the optimum to (25/6, 1), worth 31/6, which is about 5.17 — still fractional, and the bound has come down from 53/10 = 5.3. Now cut again, from the row whose basic variable is x₁: in the tableau it is (1/6)s₃ ≥ 1/6, where s₃ is the slack of the cut just added, and in the reader's variables it is x₁ + x₂ ≤ 5. One more pivot, and the relaxation stops at (5, 0), worth 5, whole.
Two cuts have driven the relaxation to the integer optimum, and the certificate is that the final corner is whole: a whole point attaining the relaxation's value is optimal for the integer problem, by the bounding theorem of the first lesson. No search tree was needed on this instance.
Now the counterexample. x₁ + x₂ ≤ 4 also removes (7/2, 9/5), and it is not a cut: it removes (3, 2), (4, 1) and (5, 0) as well, which are every optimal whole plan there is. Adding it produces a smaller region whose integer optimum is 4, and nothing in the arithmetic afterwards would reveal that the answer had been changed. Validity is a claim about all sixteen whole points of the region, and the lab tests it against every one of them.
Cutting is not a complexity result either. Each round strengthens the bound, which is worth having — a better bound closes nodes, so cuts and the search tree are used together rather than in competition. What a round of cuts does not come with is a promise about how many rounds are needed, and in practice a solver adds a few, branches, and adds more inside the tree.
Interactive
Fractional parts of a tableau row, added as a constraint, and the dual simplex puts it back
Method
Five steps, and the fourth is the one that separates a cut from an inequality you happen to like.
There may be several, and any of them will do; different rows give different cuts and all of them are valid. The lab lets you pick the row, which is the cheapest way to see that.
Exactly, on fractions. ⌊9/5⌋ = 1 with fractional part 4/5; ⌊−7/2⌋ = −4 with fractional part 1/2. Floor is not rounding, and a negative coefficient is where the difference bites.
Σ f_j x_j ≥ f₀ in the tableau's variables. Then substitute the slacks back if you want to see it in your own coordinates, which is where it can be drawn and where it is worth checking.
This is the validity claim and it is the whole lesson. One whole point on the wrong side means the inequality is not a cut, whatever it does to the fractional corner, and the point that died is the diagnosis.
The tableau is still optimal and now infeasible, so a few pivots restore it. Then look: if the corner is whole you are finished, and if it is not there is another row to cut from.
One instance, two cuts, and a third inequality that is not one. Every coefficient is exact.
The two cuts differ in an instructive way. The first is written in the original slacks and comes out as 6x₁ + 6x₂ ≤ 31, whose coefficients are ugly and whose content is simple: x₁ + x₂ ≤ 31/6. The second is derived from the slack of the first cut, and it says x₁ + x₂ ≤ 5 — the same inequality with the right-hand side pushed down to the nearest whole value the objective can reach.
The last block is the one to keep. x₁ + x₂ ≤ 4 looks exactly like the cut that worked, one unit tighter, and it silently deletes the answer. Nothing downstream complains: the relaxation solves, the corner is whole, and the reported optimum of 4 is the correct answer to a problem that was never asked.
For a faded rehearsal, derive the first cut from the second row instead — the lab has a control for the row. The supplied first move is that the derivation does not depend on which row you pick, only on that row's fractional parts, so the cut will be different and equally valid. Get 3x₁ + 5x₂ ≤ 19, check it at (7/2, 9/5) and at all three optimal plans, and say what the bound becomes.
You should be able to derive a cut from a given fractional row with exact fractional parts, write it in both the tableau's variables and your own, verify that it breaks the relaxation optimum and keeps every whole point of the region, re-solve by the dual simplex, and recognise an inequality that cuts the corner and is not valid.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.