Gomory Cutting Plane Method Example
John Mitchell

Consider the integer program

maxx        7x1  +  5x2   +   x3
subject to  2x1  +  5x2   +  2x3  ≤   9
            x ≥ 0, integer
(1)

The LP relaxation in the Gomory form is

maxx        x0
subject to  x0  -   7x1  -  5x2   -   x3          =   0
                    2x   +  5x    +  2x    +  x   =   9
                      1        2        3      4
                    x1,...,x4 ≥ 0
(2)

Pivot on the x0 entry in the first constraint to give the standard form

maxx                7x1  +  5x2   +   x3
subject to  x0  -   7x1  -  5x2   -   x3          =   0
                    2x   +  5x    +  2x    +  x   =   9
                      1        2        3      4
                    x1,...,x4 ≥ 0
(3)

Solve using (primal) simplex. The initial basic feasible solution has basic variables x0 = 0 and x4 = 9, with nonbasic variables x1 = x2 = x3 = 0. Since we are maximizing, we need all reduced costs nonpositive at optimality. So choose x1 to enter the basis. The minimum ratio test shows that we pivot in the second constraint and x4 leaves the basis:

max         63        -   25-x   -  6x   -   7x
    x       2             2  2        3     2  4
subject to  x0        +   252-x2  +  6x3  +   72x4  =   632
                  x   +   5 x   +   x   +   1x   =    9
                   1      2  2        3     2  4      2
                  x1,...,x4 ≥ 0
(4)

The new basic feasible solution has basic variables x0 = 63-
2 and x1 = 9
2, with nonbasic variables x2 = x3 = x4 = 0. This solution is optimal to the LP relaxation since all the reduced costs are nonpositive, with value 632.

Generate a Gomory cutting plane using the first constraint, since x0 is fractional. The fractional parts of the coefficients of the nonbasic variables are f2 = 1
2, f3 = 0, and f4 = 1
2. The fractional part of the right hand side is f0 = 1
2. Thus, we get the valid cutting plane

1-     1-    1-
2x2 +  2x4 ≥ 2 .
(5)

Introducing a nonnegative integer slack variable x5, this cutting plane can be written equivalently as

  1-     1-            1-
- 2x2 -  2x4 + x5 =  - 2.
(6)

Adding this constraint to the LP relaxation gives the tightened LP relaxation

maxx        63-       -   25x2  -   6x3  -   7x4
            2            225                 27                 63
subject to x0        +   -2 x2 +   6x3  +   2x4          =    2-
                 x   +    5x   +    x   +   1x           =     9
                   1      2 2        3      2 4                2
                     -    12x2           -   12x4  +   x5  =   - 12
                 x ,..., x ≥  0
                   1      5
(7)

This gives the basic (infeasible) solution with basic variables x0 = 63
 2, x1 = 9
2, and x5 = -1
2. Since the reduced costs are of the correct sign for optimality, but some of the basic variables are negative, this can be optimized using the dual simplex algorithm.

Exercise: For this problem, we could add a redundant constraint x0 0, and then the primal problem has the structure max{cT x : Ax = b,x 0}. The dual problem is then min{bT y : AT y c}. Show that the solution obtained by complementary slackness is dual feasible.

In the dual simplex method, we pick a basic variable that is negative to leave the basis. In this case, the only choice is x5, so we pivot on the third constraint. The entering variable is one of the nonbasic variables in this constraint with a negative coefficient, chosen using a minimum ratio test to ensure the reduced costs remain of the correct sign. The ratios are:

For x2: ratio is 25212 = 25. For x4: ratio is 7212 = 7.

Thus, x4 enters the basis, so we pivot on the x4 entry in the third constraint. The resulting tableau is

maxx       28        -   9x2  -   6x3          -   7x5

subject to  x0        +   9x2  +   6x3          +   7x5  =  28
                 x1  +   2x2  +    x3          +    x5  =    4

                          x2           +   x4  -   2x5  =    1
                 x1,...,x5 ≥  0
(8)

This is in optimal form: feasible with reduced costs all nonpositive (x0 = 28, x1 = 4, x4 = 1, x2 = x3 = x5 = 0). Since this solution is integral, it gives an optimal solution to the original integer program (1), namely x1 = 4, x2 = 0, x3 = 0, with optimal value x0 = 28.