A brief tutorial on Gomory mixed integer cuts (as applied to pure IPs)

In an earlier post, I gave a brief tutorial on Gomory fractional cuts. However, Gomory fractional cuts are not used in practice. A primary reason is that they are subsumed by the more general and stronger Gomory mixed integer (GMI) cuts which were introduced in a research memorandum in 1960 by Ralph Gomory.

Generality. GMI cuts apply when the problem has a mix of integer and continuous variables (MIPs), whereas Gomory fractional cuts only apply for problems in which all variables are integer (pure IPs).

Strength. When GMI cuts are applied to pure integer programs, they are just as strong or stronger than Gomory fractional cuts.

To keep things simple, I will stick with GMI decaf (i.e., as applied to pure IPs). The interested reader can consult the longer tutorial by Cornuéjols for the caffeinated version.

Note: I’m not a huge fan of how WordPress is formatting some of this post. You may find the pdf version easier to read.

The GMI cut for pure integer programs

Suppose that nonnegative integers $x_1,\dots, x_n$ satisfy the equation:

$\sum_{i=1}^n a_i x_i = b$,

where $b$ is fractional. Think of this equation as a row of the simplex tableau/dictionary.

It will help to have notations for the “fractional” parts of $b$ and each $a_i$. So, let $f := b-\lfloor b \rfloor$ and $f_i := a_i - \lfloor a_i \rfloor$. Each of these are nonnegative.

Letting $I=\{1,\dots, n\}$, the associated GMI cut is:

Notice that if $f_i \le f$ for all of the i’s, then the resulting inequality is exactly the same as the Gomory fractional cut, which can be written as:

$\sum_{i\in I} f_i x_i \ge f.$

If at least one i satisfies $f_i>f$, then the GMI cut is stronger.

Example (from here).

Consider the following IP.

Solving the LP relaxation gives the following system (with objective $z$).

This corresponds to the fractional point $(x_1,x_2,x_3,x_4)=(1.3,3.3,0,0)$.

If we apply the GMI formula for row 2 of this system, we have $f=0.3, f_1=0, f_2=0, f_3= 0.8, f_4 = 0.1$, giving the inequality $\frac{1-0.8}{1-0.3} x_3 + \frac{0.1}{0.3}x_4 \ge 1$, or equivalently:

$6 x_3 + 7x_4 \ge 21$.

Compare this to the (weaker) Gomory fractional cut $0.8x_3 + 0.1x_4 \ge 0.3$, or equivalently:

$56x_3 + 7x_4 \ge 21$.

The last row of the tableau happens to give the same GMI cut.

Unfortunately, I don’t have intuitive explanations for these GMI cuts like I had for the Gomory fractional cuts in the last post. So, let’s settle for a proof.

Proof that GMI cut is valid

(The formatting in the pdf looks nicer.)

We show that every $x^*\in S:=\left\{x \in \mathbb{Z}^n_+ ~|~\sum_{i\in I} a_ix_i = b\right\}$ satisfies inequality (1).

Consider some $x^* \in S$. This implies that $x^* \in \mathbb{Z}^n_+$ and

Since $\lfloor a_i \rfloor$ and $\lfloor b \rfloor$ and $x^*_i$ are integers, and by equation (2), we can write

for some integer $k$. In terms of our $f$ notation, this is

In the first case, suppose that $k \ge 0$, in which case

The last equation holds by (3), and the last inequality holds by $k\ge 0$.

In the second case, suppose that $k<0$. Then, $k \le -1$ since $k$ is an integer, in which case

The last equation holds by (3), and the last inequality holds by $k \le -1$.

So, $x^*$ satisfies the GMI inequality (1) in both cases, so the GMI inequality is valid for $S$.