Skip to content

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:

  1. Distinguish a mixed integer programme from a pure one.
  2. Explain why the pure Gomory cut is invalid when continuous variables are present.
  3. Derive the Gomory mixed-integer (GMI) cut.
  4. Apply the GMI cut and dual simplex to solve a MILP.
  5. 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:

\[ \begin{aligned} \max\ & Z = \sum_{j\in I}c_jx_j + \sum_{j\in C}c_jx_j\\ \text{s.t. } & A\vec x \le \vec b, \quad \vec x \ge 0\\ & x_j \ \text{integer for } j \in I, \qquad x_j \ \text{continuous for } j\in C \end{aligned} \]

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
\[ \boxed{\ \textbf{Almost every industrial optimisation model is a MILP, not a pure ILP or LP.}\ } \]

17.3 Why the Pure Cut Fails

Recall the pure Gomory derivation (L16). It rested on the claim:

\[ x_{B_r} + \sum_j \lfloor\alpha_{rj}\rfloor x_j - \lfloor\beta_r\rfloor \ \ \textbf{is an INTEGER} \]

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.

\[ \boxed{\ \textbf{Applying a pure Gomory cut to a MILP can CUT OFF the true optimum.}\ } \]

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:

\[ x_{B_r} + \sum_{j\in N} \alpha_{rj}x_j \ =\ \beta_r, \qquad f_0 = \beta_r - \lfloor\beta_r\rfloor, \quad 0 < f_0 < 1 \]

Partition the non-basic variables:

\[ N = \underbrace{N_I}_{\text{integer}} \ \cup\ \underbrace{N_C}_{\text{continuous}} \]

and define \(f_j = \alpha_{rj} - \lfloor\alpha_{rj}\rfloor\) for \(j\in N_I\).

The cut

\[ \boxed{\ \sum_{\substack{j\in N_I\\ f_j\le f_0}} \frac{f_j}{f_0}x_j \ +\ \sum_{\substack{j\in N_I\\ f_j > f_0}} \frac{1-f_j}{1-f_0}x_j \ +\ \sum_{\substack{j\in N_C\\ \alpha_{rj}>0}} \frac{\alpha_{rj}}{f_0}x_j \ -\ \sum_{\substack{j\in N_C\\ \alpha_{rj}<0}} \frac{\alpha_{rj}}{1-f_0}x_j \ \ \ge\ \ 1\ } \]

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.

  1. When all variables are integer, the GMI cut is at least as strong as the pure Gomory cut — often strictly stronger.
  2. The GMI cut is valid for MILPs, which the pure cut is not.
\[ \boxed{\ \textbf{Modern solvers use GMI cuts, not pure Gomory cuts — even on pure integer problems.}\ } \]

Simplex form

\[ -\left(\text{the left-hand side above}\right) + s_g \ =\ -1, \qquad s_g \ge 0 \]

Negative RHS ⟹ primal infeasible, dual feasible ⟹ apply dual simplex (L16 §2.3).

17.5 Worked Example

\[ \begin{aligned} \max\ & Z = 3x_1 + 4x_2\\ \text{s.t. } & 2x_1 + \ \ x_2 \le 6\\ & 2x_1 + 3x_2 \le 9\\ & x_1, x_2 \ge 0, \qquad \boxed{x_1 \ \text{INTEGER},\ \ x_2 \ \text{CONTINUOUS}} \end{aligned} \]

Step 1 — solve the LP relaxation

Intersecting the two constraints:

\[ 2x_1 + x_2 = 6, \qquad 2x_1+3x_2 = 9 \]

Subtracting: \(2x_2 = 3\), so \(x_2 = 1.5\) and \(x_1 = (6-1.5)/2 = 2.25\).

\[ x_1 = 2.25, \qquad x_2 = 1.5, \qquad Z_{LP} = 3(2.25)+4(1.5) = 6.75 + 6 = \mathbf{12.75} \]

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

\[ x_1 + \tfrac34 s_1 - \tfrac14 s_2 \ =\ \tfrac94 \]

Check: at \(s_1 = s_2 = 0\), \(x_1 = 2.25\) ✓.

Step 3 — classify the non-basic variables

\[ f_0 = \tfrac94 - 2 = \mathbf{\tfrac14} \]

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

\[ \boxed{\ 3s_1 + \tfrac13 s_2 \ \ge\ 1\ } \]

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

\[ 3(6-2x_1-x_2) + \tfrac13(9-2x_1-3x_2) \ \ge\ 1 \]
\[ 18 - 6x_1 - 3x_2 + 3 - \tfrac23x_1 - x_2 \ \ge\ 1 \]
\[ 21 - \tfrac{20}{3}x_1 - 4x_2 \ \ge\ 1 \qquad\Longrightarrow\qquad \tfrac{20}{3}x_1 + 4x_2 \ \le\ 20 \]
\[ \boxed{\ \tfrac53 x_1 + x_2 \ \le\ 5\ } \]

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

\[ \boxed{\ x_1^{*} = 2 \ (\text{integer}),\quad x_2^{*} = \tfrac53 = 1.667 \ (\text{continuous}), \quad Z^{*} = 6 + \tfrac{20}{3} = \tfrac{38}{3} \approx \mathbf{12.667}\ } \]

Verify the original constraints.

\[ 2(2) + 1.667 = 5.667 \le 6 \ \checkmark \]
\[ 2(2) + 3(1.667) = 4 + 5 = 9 \le 9 \ \checkmark \ \text{(binding)} \]

The integrality gap.

\[ Z_{LP} - Z_{MILP} = 12.75 - 12.667 = \mathbf{0.083} \qquad (0.65\%) \]

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

\[ \boxed{\ \textbf{Every additional integrality restriction widens the gap and hardens the problem.}\ } \]

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:

\[ f_0 = \tfrac14, \qquad f_{s_1} = \tfrac34 - 0 = \tfrac34, \qquad f_{s_2} = -\tfrac14 - (-1) = \tfrac34 \]
\[ \text{Pure cut: } \quad \tfrac34 s_1 + \tfrac34 s_2 \ \ge\ \tfrac14 \qquad\Longleftrightarrow\qquad s_1 + s_2 \ \ge\ \tfrac13 \]

Translate to \(x_1, x_2\).

\[ (6-2x_1-x_2) + (9-2x_1-3x_2) \ \ge\ \tfrac13 \]
\[ 15 - 4x_1 - 4x_2 \ \ge\ \tfrac13 \qquad\Longrightarrow\qquad 4x_1 + 4x_2 \le \tfrac{44}{3} \qquad\Longrightarrow\qquad x_1 + x_2 \ \le\ \tfrac{11}{3} = 3.667 \]

Now test the TRUE MILP optimum \((x_1, x_2) = (2,\ 1.667)\):

\[ x_1 + x_2 = 2 + 1.667 = 3.667 \ \le\ 3.667 \ \checkmark \ \text{(just barely satisfied)} \]

Test another valid point, \((3, 0)\):

\[ 3 + 0 = 3 \le 3.667 \ \checkmark \]

Test \((1, 2.333)\):

\[ 1 + 2.333 = 3.333 \le 3.667 \ \checkmark \]

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.

\[ \boxed{\ \textbf{The pure cut may be valid by luck, but it is never valid by proof when continuous variables are present.}\ } \]

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.

\[ f_0 = \tfrac{17}{3} - \left\lfloor\tfrac{17}{3}\right\rfloor = \tfrac{17}{3} - 5 = \mathbf{\tfrac23} \]

Step 2 — classify each non-basic variable.

\(x_3\) — INTEGER, \(\alpha = \tfrac13\).

\[ f_3 = \tfrac13 - 0 = \tfrac13 \]

Compare with \(f_0 = \tfrac23\): since \(\tfrac13 \le \tfrac23\), use \(\dfrac{f_3}{f_0}\):

\[ \text{coefficient} = \frac{1/3}{2/3} = \mathbf{\tfrac12} \]

\(x_4\) — CONTINUOUS, \(\alpha = \tfrac45 > 0\).

\[ \text{coefficient} = \frac{\alpha}{f_0} = \frac{4/5}{2/3} = \frac45\cdot\frac32 = \mathbf{\tfrac65} \]

\(s_1\) — CONTINUOUS, \(\alpha = -\tfrac12 < 0\).

\[ \text{coefficient} = \frac{-\alpha}{1-f_0} = \frac{1/2}{1/3} = \mathbf{\tfrac32} \]

Step 3 — assemble the cut.

\[ \boxed{\ \tfrac12 x_3 + \tfrac65 x_4 + \tfrac32 s_1 \ \ge\ 1\ } \]

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

\[ \frac{1-f_3}{1-f_0} = \frac{1/6}{1/3} = \frac12 \]

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

\[ -\tfrac12x_3 - \tfrac65x_4 - \tfrac32s_1 + s_g \ =\ -1 \]

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.

\[ y_1, y_2 \in \{0,1\} \quad\text{(open or not — INTEGER)} \]
\[ x_1, x_2 \ge 0 \quad\text{(units shipped — CONTINUOUS)} \]

Objective (maximise profit, ₹ lakh):

\[ \max\ Z = 0.5x_1 + 0.4x_2 - 8y_1 - 6y_2 \]

Constraints.

Capacity, linked to the open decision (the big-M pattern of L02):

\[ x_1 \le 50y_1, \qquad x_2 \le 40y_2 \]

Demand:

\[ x_1 + x_2 \le 60 \]

At most 2 warehouses (automatically satisfied here, but stated):

\[ y_1 + y_2 \le 2 \]

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.

\[ \boxed{\ \textbf{Open warehouse 1 only. Ship 50 units. } Z^{*} = ₹17\ \text{lakh.}\ } \]

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.

\[ \boxed{\ \textbf{The 10 unmet units of demand are deliberately abandoned. This is the right answer.}\ } \]

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.

\[ \text{Integrality gap} = 19.5 - 17 = \mathbf{2.5} \ (12.8\%) \]

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.

\[ \text{Progress rate} = \frac{15\% - 11\%}{200\ \text{cuts}} = \mathbf{0.02\%\ \text{per cut}} \]

At this rate, closing the remaining 11 % would need 550 more cuts, and progress typically slows further.

Why cutting planes tail off.

  1. Cuts become shallower. Early cuts slice off large chunks of the LP polytope; later ones shave thin slivers near the integer hull.
  2. 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.
  3. The tableau grows. 200 extra rows means every dual simplex pivot is far more expensive than at the start.
\[ \boxed{\ \textbf{Pure cutting planes are theoretically finite but practically unusable alone.}\ } \]

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.

  1. Stop adding cuts after ~20 per node. Diminishing returns set in quickly.
  2. Start branching on the most fractional variable, or use pseudo-cost branching.
  3. Use the 11 % gap as the incumbent bound — it is not wasted; it prunes the tree.
  4. 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.
\[ \boxed{\ \textbf{Knowing when to stop is part of solving an NP-hard problem.}\ } \]

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:

\[ \textbf{Formulation A: } \quad y \ \ge\ \frac{x}{M} = \frac{30}{1000} = \mathbf{0.03} \]
\[ \textbf{Formulation B: } \quad y \ \ge\ \frac{x}{C} = \frac{30}{50} = \mathbf{0.60} \]

With a fixed cost of ₹8 lakh per open facility:

\[ \text{A charges } 0.03\times8 = ₹0.24\ \text{lakh} \]
\[ \text{B charges } 0.60\times8 = ₹4.80\ \text{lakh} \]
\[ \text{The truth charges } 1\times8 = ₹8\ \text{lakh} \]
\[ \boxed{\ \textbf{Formulation A's relaxation understates the fixed cost by 97 \%; B's by 40 \%.}\ } \]

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.

\[ \boxed{\ \textbf{Among equivalent MILP formulations, prefer the one with the TIGHTEST LP relaxation.}\ } \]

Practical rules that follow.

  1. 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.
  2. Disaggregate constraints where possible. \(\sum_i x_i \le My\) is weaker than the set \(x_i \le M_iy\) for each \(i\).
  3. 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.

\[ \boxed{\ \textbf{Formulation quality often matters more than solver choice. A tight model beats a fast solver on a loose one.}\ } \]

17.7 Practice Problems

  1. Why is the pure Gomory cut invalid when a continuous variable has a non-zero coefficient?
  2. 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\)]
  3. Derive the GMI coefficient for a continuous variable with \(\alpha = -\tfrac25\), \(f_0 = \tfrac14\). [Ans: \((2/5)/(3/4) = 8/15\)]
  4. Classify: number of trucks, litres of fuel, whether to build, hours worked. [Ans: integer, continuous, binary, continuous]
  5. Why do fixed-charge problems have large integrality gaps?
  6. Given capacity 200, would you set \(M = 10^6\) or \(M = 200\)? Justify.
  7. 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.