General Cutting Planes

 

Consider the following integer program:

If we ignore integrality, we get the following optimal tableau (with the updated columns and reduced costs shown for nonbasic variables):

Let's look at the first constraint:

We can manipulate this to put all of the integer parts on the left side, and all the fractional parts on the right to get:

Now, note that the left hand side consists only of integers, so the right hand side must add up to an integer. Which integer can it be? Well, it consists of some positive fraction minus a series of positive values. Therefore, the right hand side can only be ; it cannot be a positive value. Therefore, we have derived the following constraint:

This constraint is satisfied by every feasible integer solution to our original problem. But, in our current solution, and both equal 0, which is infeasible to the above constraint. This means the above constraint is a cut, called the Gomory cut after its discoverer. We can now add this constraint to the linear program and be guaranteed to find a different solution, one that might be integer.

We can also generate a cut from the other constraint. Here we have to be careful to get the signs right:

gives the constraint

In general, let be defined as the largest integer less than or equal to a. For example, , , and .

If we have a constraint

with b not an integer, we can write each , for some , and for some 0 ;SPMlt; b' ;SPMlt; 1. Using the same steps we get:

to get the cut

This cut can then be added to the linear program and the problem resolved. The problem is guaranteed not to get the same solution.

This method can be shown to guarantee finding the optimal integer solution. There are a couple of disadvantages:

1. Round-off error can cause great difficulties: Is that 3.000000001 really a 3, or should I generate a cut? If I make the wrong decision I could either cut off a feasible solution (if it is really a 3 but I generate a cut) or I could end up with an infeasible solution (if it is not a 3 but I treat it as one).
2. The number of constraints that are generated can be enormous. Just like branch and bound can generate a huge number of subproblems, this technique can generate a huge number of constraints.

The combination of these makes this cutting plane technique impractical by itself. Recently however, more powerful techniques have been discovered for special problem structure. This is the subject of the next section.