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:

gmi1

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.

f1

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

f2.png

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

gmi1

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

 

gmi2

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

 

gmi2b

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

 

gmi3

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

 

gmi3b

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

 

gmi3c

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.

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s