Lesson 17: Gomory's Method for Mixed Integer Programmes¶
17.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Distinguish a mixed integer programme from a pure one.
- Explain why the pure Gomory cut is invalid when continuous variables are present.
- Derive the Gomory mixed-integer (GMI) cut.
- Apply the GMI cut and dual simplex to solve a MILP.
- Assess the convergence behaviour and practical status of cutting planes.
17.2 Mixed Integer Programmes¶
Definition. A MILP has some variables restricted to integers and others continuous:
Why MILPs dominate practice. Real models almost always mix the two:
| Integer variables | Continuous variables |
|---|---|
| number of machines to buy | hours each machine runs |
| whether to open a facility (binary) | quantity shipped from it |
| number of vehicles dispatched | fuel consumed |
| number of staff hired | overtime hours worked |
17.3 Why the Pure Cut Fails¶
Recall the pure Gomory derivation (L16). It rested on the claim:
This requires every \(x_j\) in the sum to be an integer. If a continuous variable appears with a non-zero coefficient, the expression need not be an integer, and the entire argument collapses.
This is not a matter of efficiency — it is a correctness failure. A stronger derivation is needed.
17.4 The Gomory Mixed-Integer (GMI) Cut¶
Setup¶
Take a row whose basic variable \(x_{B_r}\) must be integer but currently has a fractional value:
Partition the non-basic variables:
and define \(f_j = \alpha_{rj} - \lfloor\alpha_{rj}\rfloor\) for \(j\in N_I\).
The cut¶
Four groups, four different coefficients. This looks forbidding, but the logic is systematic:
| Variable type | Condition | Coefficient |
|---|---|---|
| integer, small fractional part | \(f_j \le f_0\) | \(\dfrac{f_j}{f_0}\) |
| integer, large fractional part | \(f_j > f_0\) | \(\dfrac{1-f_j}{1-f_0}\) |
| continuous, positive coefficient | \(\alpha_{rj} > 0\) | \(\dfrac{\alpha_{rj}}{f_0}\) |
| continuous, negative coefficient | \(\alpha_{rj} < 0\) | \(\dfrac{-\alpha_{rj}}{1-f_0}\) |
The idea behind it¶
The pure cut used "an integer less than 1 is at most 0." The GMI cut instead reasons about how far \(x_{B_r}\) must move to reach the nearest integer on either side:
- To reach \(\lfloor\beta_r\rfloor\) (below), the row must decrease by \(f_0\).
- To reach \(\lceil\beta_r\rceil\) (above), it must increase by \(1-f_0\).
Each non-basic variable contributes to one direction or the other, and its coefficient is scaled by whichever distance it helps close — hence the \(f_0\) and \(1-f_0\) denominators.
Two important properties.
- When all variables are integer, the GMI cut is at least as strong as the pure Gomory cut — often strictly stronger.
- The GMI cut is valid for MILPs, which the pure cut is not.
Simplex form¶
Negative RHS ⟹ primal infeasible, dual feasible ⟹ apply dual simplex (L16 §2.3).
17.5 Worked Example¶
Step 1 — solve the LP relaxation¶
Intersecting the two constraints:
Subtracting: \(2x_2 = 3\), so \(x_2 = 1.5\) and \(x_1 = (6-1.5)/2 = 2.25\).
\(x_1 = 2.25\) is fractional and must be integer ⟹ a cut is needed. (Note \(x_2 = 1.5\) is fine — it is allowed to be fractional.)
Step 2 — the simplex row for x₁¶
From the final tableau (both constraints binding, so \(s_1, s_2\) non-basic):
Check: at \(s_1 = s_2 = 0\), \(x_1 = 2.25\) ✓.
Step 3 — classify the non-basic variables¶
Both \(s_1\) and \(s_2\) are slack variables of constraints with a continuous variable present, so they are treated as continuous.
| Variable | \(\alpha_{rj}\) | Sign | Coefficient |
|---|---|---|---|
| \(s_1\) | \(+\tfrac34\) | positive | \(\dfrac{3/4}{f_0} = \dfrac{3/4}{1/4} = \mathbf{3}\) |
| \(s_2\) | \(-\tfrac14\) | negative | \(\dfrac{1/4}{1-f_0} = \dfrac{1/4}{3/4} = \mathbf{\tfrac13}\) |
Step 4 — the GMI cut¶
Verify it excludes the current point. At the LP optimum \(s_1 = s_2 = 0\), so the left side is \(0 < 1\) ✗ — violated ✓.
Translate into \(x_1, x_2\). With \(s_1 = 6-2x_1-x_2\) and \(s_2 = 9-2x_1-3x_2\):
Check at the LP optimum \((2.25, 1.5)\): \(\frac53(2.25) + 1.5 = 3.75 + 1.5 = 5.25 > 5\) ✗ — correctly cut off ✓.
Check at candidate integer-\(x_1\) points:
- \((2, 1.667)\): \(\frac{10}{3} + 1.667 = 5.0 \le 5\) ✓ retained
- \((3, 0)\): \(5 + 0 = 5 \le 5\) ✓ retained
- \((1, 2.333)\): \(\frac53 + 2.333 = 4.0 \le 5\) ✓ retained
No valid point is lost ✓.
Step 5 — re-solve¶
Adding the cut and running dual simplex gives
Verify the original constraints.
The integrality gap.
A very small gap — because only one variable was forced to be integer, and it moved by only 0.25.
Contrast with the pure integer version. If \(x_2\) were also required integer, the best point would be \((2, 1)\) with \(Z = 6+4 = 10\) — a much larger gap of 2.75 (21.6 %).
17.6 Solved Problems¶
Problem 1 — Why the pure cut is invalid for a MILP¶
Using the row \(x_1 + \tfrac34 s_1 - \tfrac14 s_2 = \tfrac94\) (with \(s_1, s_2\) continuous), derive the PURE Gomory cut and show it removes a valid solution.
Solution.
The pure cut (wrongly applied). Fractional parts:
Translate to \(x_1, x_2\).
Now test the TRUE MILP optimum \((x_1, x_2) = (2,\ 1.667)\):
Test another valid point, \((3, 0)\):
Test \((1, 2.333)\):
In this instance the pure cut happens not to remove the optimum — but the derivation gave no guarantee, and that is the point.
Constructing a failure. The pure cut's validity argument requires \(x_1 + \lfloor\frac34\rfloor s_1 + \lfloor-\frac14\rfloor s_2 - 2 = x_1 - s_2 - 2\) to be an integer. Since \(s_2\) is continuous, it need not be. Consider a hypothetical feasible point with \(x_1 = 2\) (integer ✓) and \(s_2 = 0.4\) (continuous, perfectly legal). Then \(x_1 - s_2 - 2 = -0.4\) — not an integer, so the chain of reasoning \(\left(\text{integer} \le f_0 < 1 \Rightarrow \text{integer}\le0\right)\) breaks.
Compare the two cuts' strength.
| Cut | In \((x_1,x_2)\) terms | Cuts off \((2.25, 1.5)\)? |
|---|---|---|
| Pure (invalid) | \(x_1+x_2 \le 3.667\) | \(3.75 > 3.667\) ✓ yes |
| GMI (valid) | \(\tfrac53x_1+x_2 \le 5\) | \(5.25 > 5\) ✓ yes |
Both cut off the LP optimum, but only the GMI cut is provably safe.
Problem 2 — Deriving a GMI cut with mixed variable types¶
From the row \(x_1 + \tfrac13 x_3 + \tfrac45 x_4 - \tfrac12 s_1 = \tfrac{17}{3}\), where \(x_1\) and \(x_3\) are integer, \(x_4\) is continuous and \(s_1\) is continuous, derive the GMI cut.
Solution.
Step 1 — the fractional part of the RHS.
Step 2 — classify each non-basic variable.
\(x_3\) — INTEGER, \(\alpha = \tfrac13\).
Compare with \(f_0 = \tfrac23\): since \(\tfrac13 \le \tfrac23\), use \(\dfrac{f_3}{f_0}\):
\(x_4\) — CONTINUOUS, \(\alpha = \tfrac45 > 0\).
\(s_1\) — CONTINUOUS, \(\alpha = -\tfrac12 < 0\).
Step 3 — assemble the cut.
Step 4 — verify. At the current LP solution all non-basic variables are 0, so the left side is \(0 < 1\) ✗ — the cut is violated, so it will exclude the current point ✓.
A contrast worth noting. Had \(x_3\)'s coefficient been \(\tfrac56\) instead (so \(f_3 = \tfrac56 > f_0 = \tfrac23\)), the rule would switch to
— the same value here, but in general the two branches differ, and using the wrong one produces an invalid cut. Always compare \(f_j\) against \(f_0\) before choosing.
Simplex form for the tableau.
Ready for dual simplex ✓.
Problem 3 — A complete MILP: facility location¶
A firm may open up to 2 warehouses (integer decision) and ships continuous quantities from them. Warehouse 1 costs ₹8 lakh to open and can ship up to 50 units; warehouse 2 costs ₹6 lakh and can ship up to 40 units. Shipping profit is ₹0.5 lakh per unit from W1 and ₹0.4 from W2. Total demand is 60 units. Formulate and solve.
Solution.
Decision variables.
Objective (maximise profit, ₹ lakh):
Constraints.
Capacity, linked to the open decision (the big-M pattern of L02):
Demand:
At most 2 warehouses (automatically satisfied here, but stated):
This is a MILP: \(y\) integer (binary), \(x\) continuous.
Solving by enumerating the four binary combinations.
| \((y_1,y_2)\) | Capacity | Best \((x_1,x_2)\) | Revenue | Fixed cost | \(Z\) |
|---|---|---|---|---|---|
| \((0,0)\) | 0 | \((0,0)\) | 0 | 0 | 0 |
| \((1,0)\) | 50 | \((50,0)\) | 25.0 | 8 | 17.0 |
| \((0,1)\) | 40 | \((0,40)\) | 16.0 | 6 | 10.0 |
| \((1,1)\) | 90, capped at 60 | \((50, 10)\) | \(25+4 = 29.0\) | 14 | 15.0 |
For \((1,1)\): fill the more profitable W1 first (₹0.5/unit) to its 50-unit capacity, then W2 for the remaining 10.
The insight. Opening both warehouses ships 10 more units (₹4 lakh extra revenue) but costs ₹6 lakh in fixed charges — a net loss of ₹2 lakh.
What the LP relaxation would say. Allowing \(y_1, y_2 \in [0,1]\), the model could "open" a fraction of a warehouse. Setting \(y_2 = 0.25\) gives capacity 10 at a cost of ₹1.5 lakh, yielding \(Z = 25 + 4 - 8 - 1.5 = 19.5\) — higher than the true optimum of 17, and completely meaningless operationally. You cannot open a quarter of a warehouse.
Why fixed-charge problems have large gaps. The LP relaxation "buys" capacity in arbitrarily small increments, spreading the fixed cost. Integrality forces the all-or-nothing decision that makes the fixed cost bite. This is why facility-location MILPs are among the harder classes.
Sensitivity. W2 becomes worth opening when its extra revenue exceeds its fixed cost: \(0.4 \times 10 > 6\), i.e. only if demand beyond W1's capacity exceeds \(6/0.4 = 15\) units. Since only 10 units remain, W2 stays closed — and would open only if total demand rose above 65.
Problem 4 — Convergence behaviour of cutting planes¶
A MILP with 20 integer variables is solved by pure cutting planes. After 200 cuts the gap has closed from 15 % to 11 %. Diagnose and recommend.
Solution.
Diagnosis: tailing off.
At this rate, closing the remaining 11 % would need 550 more cuts, and progress typically slows further.
Why cutting planes tail off.
- Cuts become shallower. Early cuts slice off large chunks of the LP polytope; later ones shave thin slivers near the integer hull.
- Numerical degradation. Each cut is derived from a tableau row containing previous cuts' coefficients. Fractions compound, denominators grow, and floating-point error accumulates until cuts become numerically invalid.
- The tableau grows. 200 extra rows means every dual simplex pivot is far more expensive than at the start.
Recommendation: switch to BRANCH AND CUT.
BRANCH AND CUT (what every modern solver does)
1. Solve the LP relaxation
2. Add a LIMITED round of strong cuts (GMI, knapsack, clique, flow cover)
-- typically 5-20 cuts per node, not hundreds
3. If still fractional, BRANCH (L18)
4. At each new node, add a few more cuts
5. Repeat
Why the hybrid works.
| Cutting planes alone | Branch and bound alone | Branch and cut | |
|---|---|---|---|
| Tightens the bound | ✓ | ✗ | ✓ |
| Guarantees finite termination | ✓ (slowly) | ✓ | ✓ |
| Tail-off problem | severe | none | avoided |
| Tree size | n/a | can explode | much smaller |
The synergy: cuts tighten the bound, which lets branch and bound fathom more nodes, which shrinks the tree; branching avoids the tail-off by changing the problem rather than shaving it.
Concrete advice for this instance.
- Stop adding cuts after ~20 per node. Diminishing returns set in quickly.
- Start branching on the most fractional variable, or use pseudo-cost branching.
- Use the 11 % gap as the incumbent bound — it is not wasted; it prunes the tree.
- Report the gap honestly. If the solver stops at 2 % after an hour, report "within 2 % of optimal" — for most business decisions that is sufficient, and pursuing the last 2 % may cost hours.
Problem 5 — Comparing formulations: the strength of the LP relaxation¶
The same fixed-charge problem can be modelled two ways. Compare their LP relaxations and explain why it matters.
Formulation A: \(\quad x \le My,\ \ M = 1000\) (a generic big number) Formulation B: \(\quad x \le Cy,\ \ C = 50\) (the actual capacity)
with \(x \ge 0\), \(y\in\{0,1\}\), capacity genuinely 50.
Solution.
Both are correct — they permit exactly the same integer solutions:
| \(y\) | Formulation A allows | Formulation B allows |
|---|---|---|
| 0 | \(x \le 0\), so \(x = 0\) ✓ | \(x\le0\), so \(x=0\) ✓ |
| 1 | \(x\le1000\), but capacity 50 caps it anyway | \(x\le50\) ✓ |
But their LP relaxations differ enormously.
Suppose the optimal \(x\) turns out to be 30. In the relaxation, \(y\) can be fractional:
With a fixed cost of ₹8 lakh per open facility:
Consequences for solution time.
| Formulation A | Formulation B | |
|---|---|---|
| LP bound | very loose | much tighter |
| Nodes fathomed early | few | many |
| Branch-and-bound tree | large | small |
| Typical solve time | minutes to hours | seconds |
The general principle.
Practical rules that follow.
- Never use a generic big M. Set \(M\) to the smallest value that is still valid — usually a real capacity, an upper bound derived from other constraints, or \(\sum_j a_j\) for a knapsack row.
- Disaggregate constraints where possible. \(\sum_i x_i \le My\) is weaker than the set \(x_i \le M_iy\) for each \(i\).
- Add valid inequalities up front if you know structural facts (e.g. "at least 2 facilities must open because total capacity of any 1 is below demand").
A cautionary note on \(M\) being too small. If \(M\) is set below the true maximum of \(x\), the model becomes wrong — it forbids legitimate solutions. Tighten \(M\) as far as provably valid, and no further.
17.7 Practice Problems¶
- Why is the pure Gomory cut invalid when a continuous variable has a non-zero coefficient?
- Derive the GMI coefficient for an integer variable with \(\alpha = \tfrac78\) when \(f_0 = \tfrac13\). [Ans: \(f_j = 7/8 > 1/3\), so \((1-7/8)/(1-1/3) = (1/8)/(2/3) = 3/16\)]
- Derive the GMI coefficient for a continuous variable with \(\alpha = -\tfrac25\), \(f_0 = \tfrac14\). [Ans: \((2/5)/(3/4) = 8/15\)]
- Classify: number of trucks, litres of fuel, whether to build, hours worked. [Ans: integer, continuous, binary, continuous]
- Why do fixed-charge problems have large integrality gaps?
- Given capacity 200, would you set \(M = 10^6\) or \(M = 200\)? Justify.
- State the branch-and-cut algorithm in five lines.
17.8 Summary¶
- A MILP mixes integer and continuous variables — the form almost all real models take.
- The pure Gomory cut is INVALID for MILPs: its derivation requires every variable in the row to be integer, and a continuous variable breaks the argument. It may cut off the true optimum.
- The GMI cut handles all four cases — integer with \(f_j\le f_0\), integer with \(f_j>f_0\), continuous positive, continuous negative — using \(f_0\) or \(1-f_0\) as the scaling denominator according to which direction the variable helps.
- The GMI cut is valid for MILPs and at least as strong as the pure cut on pure IPs; modern solvers use it exclusively.
- After adding a cut the tableau is primal infeasible, dual feasible ⟹ dual simplex.
- Cutting planes tail off: cuts become shallow, coefficients degrade numerically, and the tableau grows. The practical answer is branch and cut — a limited round of strong cuts at each node of a branch-and-bound tree.
- Formulation strength matters more than solver speed. Among equivalent models, choose the one with the tightest LP relaxation: never use a generic big \(M\) when a real capacity is available.
Next lesson: L18 — The branch-and-bound method.
Practise now: unit2-games-networks-lab.html → Integer Programming Lab: toggle variables
between integer and continuous and compare the pure Gomory and GMI cuts generated from the same row.