Skip to content

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:

  1. Formulate pure, mixed and 0–1 integer programmes.
  2. Explain why rounding the LP solution fails.
  3. Derive a Gomory fractional cut from a simplex row.
  4. Apply the dual simplex method to restore feasibility after adding a cut.
  5. 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\)
\[ \boxed{\ \textbf{Binary variables let a linear model express logical conditions — this is why MILP dominates practice.}\ } \]

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.

\[ \max\ Z = x_1 + x_2 \quad \text{s.t.}\quad 2x_1 + 2x_2 \le 3, \quad x_1, x_2 \ge 0 \ \text{integer} \]

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\).

\[ \boxed{\ \textbf{Rounding down gave 0; the true optimum is 1; the LP bound was 1.5.}\ } \]

The bounding relationship

\[ \boxed{\ Z_{IP} \ \le\ Z_{LP} \qquad \text{(for a maximisation)}\ } \]

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
\[ \boxed{\ \textbf{A cut slices off the fractional optimum while preserving every integer point.}\ } \]

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:

\[ x_{B_r} + \sum_{j\in N} \alpha_{rj}x_j \ =\ \beta_r \]

where \(N\) is the set of non-basic variables.

Split each coefficient into integer and fractional parts:

\[ \alpha_{rj} = \lfloor\alpha_{rj}\rfloor + f_{rj}, \qquad 0 \le f_{rj} < 1 \]
\[ \beta_r = \lfloor\beta_r\rfloor + f_{r}, \qquad 0 < f_{r} < 1 \]

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:

\[ x_{B_r} + \sum_j\lfloor\alpha_{rj}\rfloor x_j - \lfloor\beta_r\rfloor \ =\ f_r - \sum_j f_{rj}x_j \]

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:

\[ f_r - \sum_j f_{rj}x_j \ \le\ 0 \]
\[ \boxed{\ \sum_{j\in N} f_{rj}\,x_j \ \ge\ f_r \qquad \textbf{— the Gomory fractional cut}\ } \]

In simplex form (adding a slack \(s_g \ge 0\)):

\[ -\sum_j f_{rj}x_j + s_g = -f_r \]

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

\[ \begin{aligned} \max\ & Z = 7x_1 + 9x_2\\ \text{s.t. } & -x_1 + 3x_2 \le 6\\ & 7x_1 + x_2 \le 35\\ & x_1, x_2 \ge 0 \ \text{and integer} \end{aligned} \]

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
\[ x_1 = 4.5, \qquad x_2 = 3.5, \qquad Z_{LP} = 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:

\[ x_1 - \tfrac{1}{22}s_1 + \tfrac{3}{22}s_2 = \tfrac92 \]

Fractional parts (remember: floor rounds down for negatives):

\[ f_{s_1} = -\tfrac{1}{22} - \left\lfloor-\tfrac{1}{22}\right\rfloor = -\tfrac{1}{22} - (-1) = \tfrac{21}{22} \]
\[ f_{s_2} = \tfrac{3}{22} - 0 = \tfrac{3}{22} \]
\[ f_0 = \tfrac92 - 4 = \tfrac12 \]

The cut.

\[ \boxed{\ \tfrac{21}{22}s_1 + \tfrac{3}{22}s_2 \ \ge\ \tfrac12\ } \]

In simplex form.

\[ -\tfrac{21}{22}s_1 - \tfrac{3}{22}s_2 + s_{g} \ =\ -\tfrac12 \]

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\)):

\[ \left|\frac{28/11}{-21/22}\right| = \frac{28}{11}\cdot\frac{22}{21} = \frac{56}{21} = \frac{8}{3} \approx 2.67 \]
\[ \left|\frac{15/11}{-3/22}\right| = \frac{15}{11}\cdot\frac{22}{3} = 10 \]

Minimum is \(8/3\) ⟹ \(s_1\) enters. Pivot and continue.

Step 4 — iterate

After this and one further cut, the method converges to

\[ \boxed{\ x_1^{*} = 4,\quad x_2^{*} = 3,\quad Z^{*}_{IP} = 7(4)+9(3) = 28+27 = \mathbf{55}\ } \]

Verification.

\[ -4 + 3(3) = 5 \le 6 \ \checkmark \qquad 7(4)+3 = 31 \le 35 \ \checkmark \]

The integrality gap.

\[ Z_{LP} - Z_{IP} = 63 - 55 = \mathbf{8} \qquad (12.7\%) \]
\[ \boxed{\ \textbf{Rounding } (4.5, 3.5) \textbf{ down to } (4,3) \textbf{ happened to be right here — but see §1.2. Never rely on it.}\ } \]

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.

\[ x_1 = \frac{13}{7} = 1.857, \qquad x_2 = 0, \qquad Z_{LP} = 21\left(\tfrac{13}{7}\right) = 39 \]

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 ✗ —
\[ \boxed{\ Z^{*}_{IP} = 33 \ \text{at } (x_1, x_2) = (0, 3)\ } \]

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 —
\[ \boxed{\ \textbf{The IP optimum uses NONE of } x_1 \textbf{, while the LP optimum used ONLY } x_1.\ } \]

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.

\[ f_0 = \tfrac72 - \left\lfloor\tfrac72\right\rfloor = \tfrac72 - 3 = \mathbf{\tfrac12} \]
\[ f_{s_1} = \tfrac{7}{22} - \left\lfloor\tfrac{7}{22}\right\rfloor = \tfrac{7}{22} - 0 = \mathbf{\tfrac{7}{22}} \]
\[ f_{s_2} = \tfrac{1}{22} - 0 = \mathbf{\tfrac{1}{22}} \]

Step 2 — write the cut.

\[ \boxed{\ \tfrac{7}{22}s_1 + \tfrac{1}{22}s_2 \ \ge\ \tfrac12\ } \]

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\):

\[ \tfrac{7}{22}(6+x_1-3x_2) + \tfrac{1}{22}(35-7x_1-x_2) \ \ge\ \tfrac12 \]
\[ \tfrac{42 + 7x_1 - 21x_2 + 35 - 7x_1 - x_2}{22} \ \ge\ \tfrac12 \]
\[ \tfrac{77 - 22x_2}{22}\ \ge\ \tfrac12 \qquad\Longrightarrow\qquad \tfrac72 - x_2 \ \ge\ \tfrac12 \]
\[ \boxed{\ x_2 \ \le\ 3\ } \]

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.

\[ y_i = \begin{cases}1 & \text{if a plant is opened at site } i\\ 0 & \text{otherwise}\end{cases} \qquad i = 1,2,3,4 \]

Objective (minimise total capital cost, in ₹ lakh):

\[ \min\ Z = 50y_1 + 40y_2 + 60y_3 + 45y_4 \]

Constraints.

(a) At most 2 plants:

\[ y_1+y_2+y_3+y_4 \ \le\ 2 \]

(b) If site 1 then site 3 — the implication \(y_1 = 1 \Rightarrow y_3 = 1\):

\[ y_1 \ \le\ y_3 \]

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:

\[ y_2 + y_4 \ \le\ 1 \]

(d) At least one plant:

\[ y_1+y_2+y_3+y_4 \ \ge\ 1 \]

Binary restriction. \(y_i \in \{0,1\}\).

The complete model.

\[ \begin{aligned} \min\ & Z = 50y_1+40y_2+60y_3+45y_4\\ \text{s.t. } & y_1+y_2+y_3+y_4 \le 2\\ & y_1 - y_3 \le 0\\ & y_2+y_4 \le 1\\ & y_1+y_2+y_3+y_4 \ge 1\\ & y_i \in\{0,1\} \end{aligned} \]

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
\[ \boxed{\ \textbf{Open site 2 only. Cost = ₹40 lakh.}\ } \]

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."

\[ \boxed{\ \textbf{Binary variables encode LOGIC that no LP can express.}\ } \]

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.

\[ \boxed{\ s_g \textbf{ LEAVES}\ } \]

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\)
\[ \boxed{\ s_1 \textbf{ ENTERS} \qquad \text{pivot element} = -\tfrac{21}{22}\ } \]

Step 3 — pivot. Divide the \(s_g\) row by \(-\frac{21}{22}\):

\[ \left(0,\ 0,\ 1,\ \tfrac{3}{21},\ -\tfrac{22}{21}\ \Big|\ \tfrac{11}{21}\right) = \left(0,\ 0,\ 1,\ \tfrac17,\ -\tfrac{22}{21}\ \Big|\ \tfrac{11}{21}\right) \]

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 ✓
\[ \boxed{\ \textbf{A cut destroys feasibility but preserves optimality — precisely dual simplex's situation.}\ } \]

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.

\[ y_j = 1 \ \text{if project } j \text{ is selected, else } 0 \]
\[ \begin{aligned} \max\ & Z = 60y_1 + 42y_2 + 30y_3 + 70y_4 + 24y_5\\ \text{s.t. } & 45y_1+30y_2+25y_3+55y_4+20y_5 \ \le\ 100 && \text{(budget)}\\ & y_1 + y_4 \le 1 && \text{(mutually exclusive)}\\ & y_3 \le y_2 && \text{(3 requires 2)}\\ & y_j \in\{0,1\} \end{aligned} \]

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}\) ←
\[ \boxed{\ \textbf{Select projects 1, 2 and 3. Cost = ₹100 lakh (exactly the budget), NPV = ₹132 lakh.}\ } \]

Verify all constraints.

\[ \text{Budget: } 45+30+25 = 100 \le 100 \ \checkmark \ \text{(binding)} \]
\[ y_1+y_4 = 1+0 = 1 \le 1 \ \checkmark \]
\[ y_3 = 1 \le 1 = y_2 \ \checkmark \]

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

  1. Formulate: "at most 3 of 6 facilities, and facility 2 only if facility 5". [Ans: \(\sum y_i\le3\), \(y_2\le y_5\)]
  2. 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\)]
  3. Why does \(\lfloor -3/5\rfloor = -1\), giving fractional part \(2/5\)?
  4. LP optimum is \((2.4, 3.7)\) with \(Z = 45\). What can you say about \(Z_{IP}\)? [Ans: \(Z_{IP}\le45\)]
  5. Write the constraint for "either \(x_1\ge10\) or \(x_2\ge10\)" using a binary.
  6. State the dual simplex leaving and entering rules.
  7. 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.