The Gomory Mixed Integer Cut
John Mitchell

The derivation of the Gomory mixed integer cut exploits the mixed integer rounding approach for a simple two variable inequality. Let y be a scalar integer variable, which can be negative. Let x + be a nonnegative continuous variable. Let b be a parameter. Assume y and x satisfy the constraint

y ≤ b + x.
(1)

Assume b is non-integral, with fractional part f. Then a valid constraint is

          --1---
y ≤ ⌊b⌋ + 1 - fx,
(2)

which cuts off the point (x,y) = (0,b) that satisfies the LP relaxation of (1).

Assume we have a valid equality in nonnegative integer variables y +p and nonnegative continuous variables x +q:

      ∑           ∑
yi +      Żaijyj +      Żaijxj = b.
     j∈N1        j∈N2
(3)

The parameter b is non-integral and the terms aij are all nonzero. We relax this to the inequality

      ∑           ∑
yi +      Żaijyj +     aŻijxj ≤ b.
     j∈N         j∈N
        1           2
(4)

Let f0 > 0 denote the fractional part of b and let fj 0 denote the fractional parts of aij for j N1 N2. The set N1 can be divided using the sizes of the fractional parts fj:

       ∑                ∑             ∑
y +           Ża y  +          Ża  y +      Ża  x  ≤ b.
 i             ij j              ij j        ij j
     j∈N1:fj≤f0        j∈N1:fj>f0        j∈N2
(5)

By splitting aij into integer and fractional parts for j N1, this can be written equivalently as

y + ∑           ⌊Ża ⌋y  + ∑           ⌈Ża ⌉y
 i     j∈N1:fj≤f0  ij  j      j∈N1:fj>f0  ij  j
         ≤ b - ∑           f y +  ∑          (1 - f )y  -  ∑     Ża  x .
                 j∈N1:fj≤f0  j j     j∈N1:fj>f0      j  j     j∈N2  ij j
(6)

This can be weakened by removing terms from the right hand side which must be nonpositive:

    ∑                    ∑
yi +            ⌊Żaij⌋yj +             ⌈Żaij⌉yj
       j∈N1:fj≤f0            j∈N1:fj>f0
         ≤ b + ∑          (1 - fj)yj - ∑          Żaijxj.
                 j∈N1:fj>f0               j∈N2:Żaij<0
(7)

(This is the step where we need y to be nonnegative.)

This inequality is now in the form of (1), with the correspondence

            ∑                    ∑
 y  =  yi +    j∈N1:fj≤f0⌊Żaij⌋yj +   j∈N1:fj>f0⌈Żaij⌉yj
       ∑                       ∑
x   =     j∈N1:fj>f0(1 - fj)yj -    j∈N2:Żaij<0 Żaijxj.
(8)

Thus the construction of (2) gives us the valid constraint

     ∑                    ∑
yi +    j∈N1:fj≤f0⌊Żaij⌋yj +    j∈N1:fj>f0⌈Żaij⌉yj
                  ∑           1- f      ∑           Ża
         ≤  ⌊b⌋ +   j∈N1:fj>f0 1--f0jyj -   j∈N2:Żaij<01-ijf0xj.
(9)

Note that

        1 --fj                   1 --fj        f0(1---fj)
⌈Żaij⌉ - 1 - f0 = Żaij + (1 - fj) - 1 - f0 = Żaij -  1 - f0
(10)

and that

--Żaij--         f0Żaij-
1 - f0 = Żaij + 1 - f0.
(11)

Collecting variables on the left hand side, (9) is equivalent to

                                          (            )
yi + ∑          (Żaij - fj)yj + ∑           Żaij - f0(1-fj) yj
       j∈N1:fj≤f0                 j∈N1:fj>f0        1-f0
                 ∑          (      f0Żaij)
              +    j∈N2:Żaij<0 Żaij + 1-f0  xj ≤ ⌊b⌋.
(12)

Thus, by exploiting the equality (3), we can write (9) in the equivalent form

∑                  ∑                      ∑                   ∑
   j∈N1:f ≤f0 fjyj +  j∈N1:f>f0 f0(11--ffj)yj +    j∈N2:Ża >0 Żaijxj -    j∈N2:Ża  <0 f10-Żafijxj ≥ f0.
        j                 j        0              ij                 ij     0
(13)

This is the Gomory mixed integer cut.

References

[1]   G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John Wiley, New York, 1988.

[2]   L. A. Wolsey. Integer Programming. John Wiley, New York, 1998.