Gomory's Cutting Plane Method

Solves a pure IPP by adding constraints (cuts) to the LP relaxation’s optimal tableau that exclude the fractional solution without excluding any feasible integer solution.

Fractional Cut

For a basic variable $x_i$ with a fractional value in the optimal tableau’s row:

Split each coefficient into integer and fractional parts, $a_{ij} = \lfloor a_{ij} \rfloor + f_{ij}$ and $b_i = \lfloor b_i \rfloor + f_i$ (with $0 \le f_{ij}, f_i < 1$). The Gomory constraint is:

Steps

• Solve the LP relaxation with simplex.
• If every basic variable is integral, stop; the solution is optimal for the IPP.
• Otherwise, pick a row with a fractional basic variable and derive its Gomory constraint.
• Add the constraint (as a new row with a surplus variable) to the tableau and resolve with the dual simplex method, since the new RHS is negative.
• Repeat until every basic variable is integral.