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.
Solving the LP relaxation gives the following system (with objective ).
This corresponds to the fractional point .
A first cut
In any feasible solution to the IP, will take an integer value, so, from the second row, we can write for some integer . Notice that the left side of this equation can only take nonnegative values, so the right side must as well, i.e., or . Since is an integer, we know that . So, . We have thus argued for the validity of the Gomory fractional cut:
Note that this inequality cuts off our fractional point .
A second cut
Now consider the last row . As before, we can write for some integer . However, the left side of this equation may not always take nonnegative values (due to the negative coefficient for ), so our previous argument will not work. However, if we add to both sides, we can write for some (other) integer . Using the same argument as before, we can generate the (same) Gomory fractional cut:
Gomory fractional cuts in general
We can write the Gomory fractional cut in more general terms as follows. Suppose that nonnegative integers satisfy the equation:
where is fractional, i.e., . Think of this equation as a row of the simplex tableau/dictionary. The associated Gomory fractional cut is:
Proposition. The Gomory fractional cut is valid for the set .
Proof. Let . We are to show that . By , we know that . Since each is integer, and since each is integer, we can write:
for some integer . Observe that the left side is nonnegative, so and thus . By , this implies . In conclusion,
- Subtracting from in the Gomory fractional cut ensures that the left side is nonnegative, which was key to our arguments. We could have instead subtracted some from and the resulting inequality would remain valid; however, this would weaken the inequality.
- The Gomory fractional cut remains valid when you add other constraints to the set . This means you can still use it when your IP is more complicated.