Lesson 16: Integer Programming and Gomory's Cutting-Plane Method¶
16.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Formulate pure, mixed and 0–1 integer programmes.
- Explain why rounding the LP solution fails.
- Derive a Gomory fractional cut from a simplex row.
- Apply the dual simplex method to restore feasibility after adding a cut.
- Solve a pure integer programme by the cutting-plane method.
16.2 Integer Programming¶
Definition. An integer linear programme (ILP) is an LP with some or all variables restricted to integers.
| Type | Restriction |
|---|---|
| Pure integer (PIP) | all variables integer |
| Mixed integer (MILP) | some variables integer |
| 0–1 (binary) | all variables in \(\{0,1\}\) |
Why we need it. LP's divisibility assumption (L02) fails whenever the answer must be a whole number: aircraft, machines, staff, plant locations, yes/no decisions.
Modelling with binary variables¶
Binary variables are far more powerful than "counting indivisible items" — they encode logic.
| Requirement | Constraint |
|---|---|
| At most one of A, B | \(y_A + y_B \le 1\) |
| Exactly one of A, B, C | \(y_A+y_B+y_C = 1\) |
| If A then B | \(y_A \le y_B\) |
| A and B together or neither | \(y_A = y_B\) |
| Fixed cost \(F\) if \(x>0\) | \(x \le My\), cost term \(Fy\) |
| Either \(g_1\le0\) or \(g_2\le0\) | \(g_1 \le My\), \(g_2\le M(1-y)\) |
| At least \(k\) of \(n\) | \(\sum_i y_i \ge k\) |
Why rounding fails¶
Two independent failure modes.
(1) The rounded point may be INFEASIBLE. If the LP optimum lies on a constraint boundary, rounding up leaves the feasible region.
(2) The rounded point may be feasible but FAR from optimal. The integer optimum can be at a completely different vertex.
A concrete example.
LP relaxation: any point with \(x_1+x_2 = 1.5\), so \(Z_{LP} = 1.5\). Rounding \((0.75, 0.75)\) up: \((1,1)\) gives \(2+2 = 4 > 3\) — INFEASIBLE. Rounding down: \((0,0)\), \(Z = 0\). True integer optimum: \((1,0)\) or \((0,1)\), \(Z = 1\).
The bounding relationship¶
The LP relaxation always gives an upper bound, because relaxing the integrality constraint can only enlarge the feasible set. This bound is the foundation of both cutting planes and branch and bound.
Complexity. ILP is NP-hard. There is no known polynomial algorithm, and none is expected — in stark contrast to LP.
16.3 Gomory's Cutting-Plane Method (1958)¶
The idea¶
1. Solve the LP relaxation (ignore integrality)
2. If the solution is all-integer -> DONE
3. Otherwise, generate a CUT: a linear inequality that
- is violated by the current fractional LP solution
- is satisfied by EVERY integer feasible point
4. Add the cut and re-solve
5. Repeat
Ralph Gomory proved in 1958 that this terminates in finitely many steps — the first finite exact algorithm for integer programming.
Deriving the fractional cut¶
Take any simplex row with a fractional basic-variable value:
where \(N\) is the set of non-basic variables.
Split each coefficient into integer and fractional parts:
Note carefully: the floor of a negative number rounds down, so \(\lfloor -1/22\rfloor = -1\) and \(f = -1/22 - (-1) = 21/22\).
Substituting and rearranging:
The left side is an integer (for any integer feasible solution), so the right side must be too. Since \(x_j \ge 0\) and \(f_{rj}\ge0\), the right side is at most \(f_r < 1\). An integer less than 1 is at most 0:
In simplex form (adding a slack \(s_g \ge 0\)):
The negative right-hand side is the point: the current solution has all non-basic \(x_j = 0\), so \(s_g = -f_r < 0\) — infeasible, exactly as intended. The cut has excluded the current point.
Restoring feasibility — the dual simplex method¶
The new row is primal infeasible (negative RHS) but dual feasible (all \(z_j-c_j\ge0\)). The dual simplex method handles precisely this case.
DUAL SIMPLEX
1. LEAVING variable: the row with the MOST NEGATIVE RHS
2. ENTERING variable: among columns j with a NEGATIVE entry a_rj in that row,
choose j minimising | (z_j - c_j) / a_rj |
3. Pivot as usual
4. Repeat until all RHS >= 0 -> feasible AND optimal
If no negative entry exists in the leaving row, the problem is INFEASIBLE.
Which row to cut from. Choose the row with the largest fractional part \(f_r\) — it generally produces a deeper cut and faster convergence.
16.4 Worked Example¶
Step 1 — solve the LP relaxation¶
Adding slacks and running simplex:
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_2\) | 9 | 0 | 1 | \(7/22\) | \(1/22\) | \(\mathbf{7/2}\) |
| \(x_1\) | 7 | 1 | 0 | \(-1/22\) | \(3/22\) | \(\mathbf{9/2}\) |
| \(z_j-c_j\) | 0 | 0 | \(28/11\) | \(15/11\) | 63 |
Both fractional ⟹ a cut is needed. Note \(Z_{IP} \le 63\).
Step 2 — generate a cut¶
Both rows have fractional part \(f = 1/2\); take the \(x_1\) row:
Fractional parts (remember: floor rounds down for negatives):
The cut.
In simplex form.
Verify the cut is valid. Substituting \(s_1 = 6 + x_1 - 3x_2\) and \(s_2 = 35 - 7x_1 - x_2\) and simplifying yields a constraint in \(x_1, x_2\) satisfied by every integer point of the region but violated by \((4.5, 3.5)\) — which is exactly the definition of a cut.
Step 3 — dual simplex¶
Append the cut row and pivot. The most negative RHS is \(-\frac12\) (the cut row). Among its negative entries \(-\frac{21}{22}\) (column \(s_1\)) and \(-\frac{3}{22}\) (column \(s_2\)):
Minimum is \(8/3\) ⟹ \(s_1\) enters. Pivot and continue.
Step 4 — iterate¶
After this and one further cut, the method converges to
Verification.
The integrality gap.
16.5 Solved Problems¶
Problem 1 — Why rounding fails, quantified¶
Solve \(\max\ Z = 21x_1 + 11x_2\) s.t. \(7x_1+4x_2\le13\), \(x_1,x_2\ge0\) integer. Compare the LP optimum, the rounded solutions and the true integer optimum.
Solution.
LP relaxation. Compare value per unit of resource: \(x_1\) gives \(21/7 = 3\) and \(x_2\) gives \(11/4 = 2.75\). So \(x_1\) dominates.
Rounding down. \((1, 0)\): feasible (\(7 \le 13\) ✓), \(Z = 21\).
Rounding up. \((2, 0)\): \(14 > 13\) ✗ — INFEASIBLE.
Rounding down and using the slack. With \(x_1 = 1\), slack \(= 13-7 = 6\), so \(x_2 \le 6/4 = 1.5\) ⟹ \(x_2 = 1\). Point \((1,1)\): \(7+4 = 11\le13\) ✓, \(Z = 21+11 = 32\).
True integer optimum. Enumerate feasible integer points:
| \((x_1,x_2)\) | \(7x_1+4x_2\) | Feasible | \(Z\) |
|---|---|---|---|
| \((0,0)\) | 0 | ✓ | 0 |
| \((0,1)\) | 4 | ✓ | 11 |
| \((0,2)\) | 8 | ✓ | 22 |
| \((0,3)\) | 12 | ✓ | 33 |
| \((1,0)\) | 7 | ✓ | 21 |
| \((1,1)\) | 11 | ✓ | 32 |
| \((1,2)\) | 15 | ✗ | — |
The comparison — this is the point of the problem.
| Approach | Solution | \(Z\) | Error |
|---|---|---|---|
| LP relaxation | \((1.857, 0)\) | 39 | — (upper bound) |
| Round down | \((1,0)\) | 21 | −36 % |
| Round + fill slack | \((1,1)\) | 32 | −3 % |
| True IP optimum | \(\mathbf{(0,3)}\) | 33 | — |
Why the reversal. \(x_1\) has the better ratio (3 versus 2.75), which is what LP exploits — but \(x_1\) comes in indivisible chunks of 7, wasting resource. Three units of \(x_2\) consume exactly 12 of the 13 available, wasting only 1.
The general lesson. The integer optimum can be structurally different from the LP optimum, not merely a rounded version of it. This is why integer programming needs its own algorithms.
Problem 2 — Deriving a Gomory cut¶
From the simplex row \(x_2 + \tfrac{7}{22}s_1 + \tfrac{1}{22}s_2 = \tfrac72\), derive the Gomory cut.
Solution.
Step 1 — identify fractional parts.
Step 2 — write the cut.
Step 3 — verify it excludes the current point. At the LP optimum, \(s_1 = s_2 = 0\) (both are non-basic), so the left side is \(0 < \frac12\) ✗ — the cut is violated ✓, as required.
Step 4 — verify it keeps all integer points. Rewrite in terms of \(x_1, x_2\) using \(s_1 = 6+x_1-3x_2\) and \(s_2 = 35-7x_1-x_2\):
A beautifully interpretable cut. The LP said \(x_2 = 3.5\); the cut says \(x_2 \le 3\) — exactly the "round down" that integrality demands, derived automatically.
Check it preserves integer points. Any integer feasible point has \(x_2\) integer with \(-x_1+3x_2\le6\); since \(x_1 \le 5\) (from \(7x_1\le35\)), \(3x_2 \le 6+5 = 11\), so \(x_2\le3.67\), hence \(x_2\le3\) for integers ✓ — no integer point is lost.
Compare with the cut from the \(x_1\) row (§3): \(\frac{21}{22}s_1 + \frac{3}{22}s_2 \ge \frac12\). Both are valid; the \(x_2\)-row cut happens to be the cleaner one here. In practice, generate cuts from several rows and add the deepest.
Problem 3 — Modelling with binary variables¶
A firm may open plants at 4 sites. Site 1 costs ₹50 lakh, site 2 ₹40, site 3 ₹60, site 4 ₹45. Constraints: (a) at most 2 plants; (b) if site 1 opens then site 3 must also open; (c) sites 2 and 4 are mutually exclusive; (d) at least one plant must open. Formulate.
Solution.
Decision variables.
Objective (minimise total capital cost, in ₹ lakh):
Constraints.
(a) At most 2 plants:
(b) If site 1 then site 3 — the implication \(y_1 = 1 \Rightarrow y_3 = 1\):
Check the logic table:
| \(y_1\) | \(y_3\) | \(y_1\le y_3\) | Allowed? |
|---|---|---|---|
| 0 | 0 | \(0\le0\) ✓ | yes |
| 0 | 1 | \(0\le1\) ✓ | yes (3 alone is fine) |
| 1 | 0 | \(1\le0\) ✗ | correctly blocked |
| 1 | 1 | \(1\le1\) ✓ | yes |
(c) Sites 2 and 4 mutually exclusive:
(d) At least one plant:
Binary restriction. \(y_i \in \{0,1\}\).
The complete model.
Solving by enumeration (\(2^4 = 16\) cases, of which few are feasible):
| Solution | Feasible? | Cost |
|---|---|---|
| \((0,1,0,0)\) | ✓ all constraints | 40 ← |
| \((0,0,0,1)\) | ✓ | 45 |
| \((0,0,1,0)\) | ✓ | 60 |
| \((1,0,1,0)\) | ✓ (2 plants, 1⟹3 ✓) | 110 |
| \((1,0,0,0)\) | ✗ violates \(y_1\le y_3\) | — |
| \((0,1,0,1)\) | ✗ violates \(y_2+y_4\le1\) | — |
| \((0,1,1,0)\) | ✓ | 100 |
Note what the LP relaxation would give. Relaxing to \(0\le y_i\le1\), the cheapest way to satisfy \(\sum y_i \ge 1\) is \(y_2 = 1\) (cost 40) — the same answer here. But that is luck. Had constraint (a) been \(\sum y_i \le 1.5\), the LP would return a fractional solution with no meaning: "open 1.5 plants."
Problem 4 — The dual simplex method after a cut¶
The tableau below has become primal infeasible after adding a cut. Perform one dual simplex iteration.
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_g\) | RHS |
|---|---|---|---|---|---|---|---|
| \(x_2\) | 9 | 0 | 1 | \(7/22\) | \(1/22\) | 0 | \(7/2\) |
| \(x_1\) | 7 | 1 | 0 | \(-1/22\) | \(3/22\) | 0 | \(9/2\) |
| \(s_g\) | 0 | 0 | 0 | \(-21/22\) | \(-3/22\) | 1 | \(-1/2\) |
| \(z_j-c_j\) | 0 | 0 | \(28/11\) | \(15/11\) | 0 | 63 |
Solution.
Step 1 — leaving variable. The most negative RHS is \(-\frac12\) in the \(s_g\) row.
Step 2 — entering variable. Consider only columns with a negative entry in the \(s_g\) row:
| Column | \(a_{rj}\) | \(z_j-c_j\) | \(\left\lvert\dfrac{z_j-c_j}{a_{rj}}\right\rvert\) |
|---|---|---|---|
| \(s_1\) | \(-21/22\) | \(28/11\) | \(\dfrac{28/11}{21/22} = \dfrac{28}{11}\cdot\dfrac{22}{21} = \dfrac{8}{3} \approx 2.67\) ← min |
| \(s_2\) | \(-3/22\) | \(15/11\) | \(\dfrac{15/11}{3/22} = \dfrac{15}{11}\cdot\dfrac{22}{3} = 10\) |
Step 3 — pivot. Divide the \(s_g\) row by \(-\frac{21}{22}\):
Then eliminate \(s_1\) from the other rows:
Row \(x_2\): subtract \(\frac{7}{22}\times\)(new pivot row). Row \(x_1\): subtract \(-\frac{1}{22}\times\)(new pivot row), i.e. add \(\frac{1}{22}\times\).
Step 4 — check. All RHS values are now \(\ge 0\) (feasible) and all \(z_j-c_j \ge 0\) (optimal). If the basic variables are all integers, we are done; otherwise generate another cut.
Why dual simplex, and not ordinary simplex?
| Primal simplex | Dual simplex | |
|---|---|---|
| Maintains | feasibility, seeks optimality | optimality, seeks feasibility |
| Starts from | feasible but suboptimal | optimal but infeasible |
| After a cut | would need a full restart | continues from where we were ✓ |
This is why cutting planes are efficient in practice: each new cut requires only a few dual simplex pivots, not a complete re-solve.
Problem 5 — A capital-budgeting application¶
A firm has ₹100 lakh to invest across 5 projects. Formulate the selection problem and solve.
| Project | Cost (₹ lakh) | NPV (₹ lakh) |
|---|---|---|
| 1 | 45 | 60 |
| 2 | 30 | 42 |
| 3 | 25 | 30 |
| 4 | 55 | 70 |
| 5 | 20 | 24 |
Additionally: projects 1 and 4 are mutually exclusive (same market), and project 3 requires project 2 (shared infrastructure).
Solution.
Formulation.
Solution by enumeration of promising combinations.
| Selection | Cost | Feasible? | NPV |
|---|---|---|---|
| \(\{4, 2\}\) | \(55+30 = 85\) | ✓ | \(70+42 = 112\) |
| \(\{4, 3\}\) | \(55+25 = 80\) | ✗ (3 needs 2) | — |
| \(\{1, 2, 5\}\) | \(45+30+20 = 95\) | ✓ | \(60+42+24 = 126\) |
| \(\{4, 5\}\) | \(55+20 = 75\) | ✓ | \(70+24 = 94\) |
| \(\{1, 3\}\) | \(45+25 = 70\) | ✗ (3 needs 2) | — |
| \(\{2,3,5\}\) | \(30+25+20 = 75\) | ✓ | \(42+30+24 = 96\) |
| \(\{1, 2\}\) | \(45+30 = 75\) | ✓ | \(102\) |
| \(\{4, 2, 5\}\) | \(55+30+20 = 105\) | ✗ (over budget) | — |
| \(\{1,2,3\}\) | \(45+30+25 = 100\) | ✓ | \(60+42+30 = \mathbf{132}\) ← |
Verify all constraints.
Comparison with the LP relaxation. Ranking by NPV per rupee:
| Project | NPV/cost |
|---|---|
| 2 | \(42/30 = 1.40\) |
| 5 | \(24/20 = 1.20\) |
| 3 | \(30/25 = 1.20\) |
| 4 | \(70/55 = 1.27\) |
| 1 | \(60/45 = 1.33\) |
Greedy on this ratio would take 2 (30), then 1 (45, running 75), then 4 — but 4 conflicts with 1; then 3 (25, running 100). Result: \(\{2,1,3\}\), NPV 132 — the same, by luck.
But the greedy ratio rule is NOT reliable. Change project 5's NPV to 40 (ratio 2.0, the best) and greedy would take 5 first, then 2, then 1 (cost \(20+30+45 = 95\), NPV \(40+42+60 = 142\)) — while the true optimum might differ. Only exact methods guarantee the answer.
The integrality gap. The LP relaxation allows fractional projects: take 2 (30), 1 (45), then \(25/25 = 1\) of project 3 — exactly 100, NPV 132. Here \(Z_{LP} = Z_{IP} = 132\), so the gap is zero and the LP solution happens to be integral.
When the gap matters. Had the budget been ₹90 lakh, the LP would take a fraction of a project (meaningless), and the IP answer would be strictly worse than the LP bound. The gap is the price of indivisibility.
Advice to the board. "Fund projects 1, 2 and 3 for ₹100 lakh, returning ₹132 lakh NPV. Note the budget is exactly binding — the shadow price analysis (L07) would tell you what an extra ₹10 lakh is worth, and given project 5's ratio of 1.20 it would be worth about ₹12 lakh. Consider seeking additional funding."
16.6 Practice Problems¶
- Formulate: "at most 3 of 6 facilities, and facility 2 only if facility 5". [Ans: \(\sum y_i\le3\), \(y_2\le y_5\)]
- Derive the Gomory cut from the row \(x_1 + \tfrac25 s_1 - \tfrac35 s_2 = \tfrac{12}{5}\). [Ans: \(\tfrac25 s_1 + \tfrac25 s_2 \ge \tfrac25\)]
- Why does \(\lfloor -3/5\rfloor = -1\), giving fractional part \(2/5\)?
- LP optimum is \((2.4, 3.7)\) with \(Z = 45\). What can you say about \(Z_{IP}\)? [Ans: \(Z_{IP}\le45\)]
- Write the constraint for "either \(x_1\ge10\) or \(x_2\ge10\)" using a binary.
- State the dual simplex leaving and entering rules.
- Give two reasons rounding an LP solution is unsafe.
16.7 Summary¶
- ILP restricts variables to integers: pure, mixed or 0–1. Binary variables encode logic — implications, exclusivity, fixed costs, either/or — which plain LP cannot express.
- Rounding fails two ways: the rounded point may be infeasible, or feasible but far from optimal. The integer optimum can be structurally different from the LP optimum.
- \(Z_{IP}\le Z_{LP}\) always (maximisation) — the relaxation is an upper bound, and the difference is the integrality gap.
- Gomory cut from a fractional row: \(\sum_j f_{rj}x_j \ge f_r\), where \(f = \alpha - \lfloor\alpha\rfloor\) (floor rounds down, including for negatives). The cut excludes the current fractional point but no integer point.
- Adding a cut makes the tableau primal infeasible but dual feasible — exactly the dual simplex situation: leave on the most negative RHS, enter on \(\min|(z_j-c_j)/a_{rj}|\) over negative entries.
- Cuts often have clean interpretations (\(x_2\le3\) in the worked example) — check this, as it validates the derivation.
- ILP is NP-hard; Gomory's method terminates finitely but can be slow. Modern solvers combine cuts with branch and bound (L18) — "branch and cut."
Next lesson: L17 — Gomory's method for mixed integer programmes.
Practise now: unit2-games-networks-lab.html → Integer Programming Lab: solve the LP relaxation,
see the fractional vertex, generate cuts and watch the feasible region shrink toward the integer hull.