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