The Gomory Mixed Integer Cut
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
Assume b is non-integral, with fractional part f. Then a valid constraint is
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:
The parameter b is non-integral and the terms aij are all nonzero. We relax this to the inequality
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:
By splitting aij into integer and fractional parts for j ∈ N1, this can be written equivalently as
This can be weakened by removing terms from the right hand side which must be nonpositive:
(This is the step where we need y to be nonnegative.)
This inequality is now in the form of (1), with the correspondence
Thus the construction of (2) gives us the valid constraint
Collecting variables on the left hand side, (9) is equivalent to
Thus, by exploiting the equality (3), we can write (9) in the equivalent form
This is the Gomory mixed integer cut.