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 satisfy the equation:

,

where 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 and each . So, let and . Each of these are nonnegative.

Letting , the associated GMI cut is:

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

If at least one i satisfies , then the GMI cut is stronger.

### Example (from here).

Consider the following IP.

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

This corresponds to the fractional point .

If we apply the GMI formula for row 2 of this system, we have , giving the inequality , or equivalently:

.

Compare this to the (weaker) Gomory fractional cut , or equivalently:

.

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 satisfies inequality (1).

Consider some . This implies that and

Since and and are integers, and by equation (2), we can write

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

In the first case, suppose that , in which case

The last equation holds by (3), and the last inequality holds by .

In the second case, suppose that . Then, since is an integer, in which case

The last equation holds by (3), and the last inequality holds by .

So, satisfies the GMI inequality (1) in both cases, so the GMI inequality is valid for .