A brief tutorial on Gomory fractional cuts

Integer programs (IPs) are solved in practice by branch-and-cut algorithms. These algorithms rely heavily on the effective use of cutting planes, which are inequalities that are added to linear programming (LP) relaxations to cut off (bad) fractional points, but not the (good) integer feasible points. The classical cutting planes for solving arbitrary IPs were developed by Ralph Gomory in the late 1950s.

Prior to working on IP, Gomory earned his PhD in mathematics from Princeton in 1954, after which he spent a few years with the US Navy. In 1957, he went back to Princeton, but was retained as a consultant for the Navy. Gomory later recounted that his involvement with the Navy led him to IP:

As the Navy had kept me on as a consultant I continued to work on Navy problems through monthly trips to Washington. On one of these trips a group presented a linear programming model of a Navy Task Force. One of the presenters remarked that it would be nice to have whole number answers as 1.3 aircraft carriers, for example, was not directly usable.

Within the next few weeks, Gomory had developed his technique for generating cutting planes based on the simplex tableau. Soon after, he proved that his algorithm was finite and programmed it on the E101, allowing him to solve 5-variable problems reliably.

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

A first cut

In any feasible solution to the IP, x_2 will take an integer value, so, from the second row, we can write 0.8x_3+0.1x_4=0.3+k for some integer k. Notice that the left side of this equation can only take nonnegative values, so the right side must as well, i.e.,  0.3 +k \ge 0 or k \ge  - 0.3. Since k is an integer, we know that k \ge 0. So, 0.8x_3 + 0.1x_4 = 0.3+k \ge 0.3. We have thus argued for the validity of the Gomory fractional cut:

0.8x_3 + 0.1x_4 \ge 0.3.

Note that this inequality cuts off our fractional point (1.3,3.3,0,0).

A second cut

Now consider the last row x_1 -0.2x_3 + 0.1x_4 =1.3. As before, we can write -0.2x_3+0.1x_4=0.3+k for some integer k. However, the left side of this equation may not always take nonnegative values (due to the negative coefficient for x_3), so our previous argument will not work. However, if we add x_3 to both sides, we can write 0.8x_3+0.1x_4=0.3+p for some (other) integer p. Using the same argument as before, we can generate the (same) Gomory fractional cut:

0.8x_3 + 0.1x_4 \ge 0.3.

Gomory fractional cuts in general

We can write the Gomory fractional cut in more general terms as follows. Suppose that nonnegative integers x_1,\dots, x_n satisfy the equation:

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

where a_0 is fractional, i.e., a_0 \notin \mathbb{Z}. Think of this equation as a row of the simplex tableau/dictionary. The associated Gomory fractional cut is:

\sum_{i=1}^n (a_i -\lfloor a_i \rfloor) x_i \ge a_0 - \lfloor a_0\rfloor.

Proposition. The Gomory fractional cut is valid for the set X=\{ x \in \mathbb{Z}^n_+ ~|~\sum_{i=1}^n a_i x_i = a_0\}.

Proof. Let x^* \in X. We are to show that \sum_{i=1}^n (a_i -\lfloor a_i \rfloor) x^*_i \ge a_0 - \lfloor a_0\rfloor. By x^* \in X, we know that \sum_{i=1}^n a_i x^*_i = a_0. Since each \lfloor a_i\rfloor is integer, and since each x^*_i is integer, we can write:

\sum_{i=1}^n (a_i -\lfloor a_i \rfloor) x^*_i = a_0 - \lfloor a_0\rfloor +k,

for some integer k. Observe that the left side is nonnegative, so a_0 - \lfloor a_0\rfloor +k \ge 0 and thus k \ge \lfloor a_0\rfloor-a_0 > -1. By k \in \mathbb{Z}, this implies k\ge 0. In conclusion,

\sum_{i=1}^n (a_i -\lfloor a_i \rfloor) x^*_i = a_0 - \lfloor a_0\rfloor +k \ge a_0 - \lfloor a_0\rfloor. Q.E.D.

 

Two observations:

  1. Subtracting \lfloor a_i \rfloor from a_i in the Gomory fractional cut ensures that the left side is nonnegative, which was key to our arguments. We could have instead subtracted some q < \lfloor a_i \rfloor from a_i and the resulting inequality would remain valid; however, this would weaken the inequality.
  2. The Gomory fractional cut remains valid when you add other constraints to the set X. This means you can still use it when your IP is more complicated.
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