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

 (1)

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

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

 (3)

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

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

 (5)

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

 (6)

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

 (7)

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

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

 (8)

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

 (9)

Note that

 (10)

and that

 (11)

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

 (12)

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

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