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.

Worked Example

Same LP as the branch and bound worked example: maximize $Z = 2x_1 + 3x_2$ subject to $x_1 + x_2 \le 5$, $2x_2 \le 7$, $x_1, x_2 \ge 0$ and integer, with LP relaxation optimum $x_1 = 1.5$, $x_2 = 3.5$, $Z = 13.5$.

Standard form: $x_1 + x_2 + s_1 = 5$, $x_2 + 0.5s_2 = 3.5$.

Optimal tableau rows, basis $x_1, x_2$:

The $x_1$ row has $b_1 = 1.5$, so $f_1 = 0.5$. Its coefficients split as $f_{1,s_1} = 0$ (since $1$ is already an integer) and $f_{1,s_2} = 0.5$ (since $-0.5 = \lfloor -0.5 \rfloor + 0.5$).

Gomory constraint: $0.5s_2 \ge 0.5$, i.e. $s_2 \ge 1$.

Optimal solution: $x_1 = 2$, $x_2 = 3$, $Z = 13$. Matches branch and bound.