next up previous contents
Next: Cuts for Special Structure Up: Cutting Plane Techniques Previous: Cutting Plane Techniques

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 tex2html_wrap_inline1861 ; 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, tex2html_wrap_inline1863 and tex2html_wrap_inline1865 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 tex2html_wrap_inline1867 be defined as the largest integer less than or equal to a. For example, tex2html_wrap_inline1871 , tex2html_wrap_inline1873 , and tex2html_wrap_inline1875 .

If we have a constraint


with b not an integer, we can write each tex2html_wrap_inline1879 , for some tex2html_wrap_inline1881 , and tex2html_wrap_inline1883 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.

next up previous contents
Next: Cuts for Special Structure Up: Cutting Plane Techniques Previous: Cutting Plane Techniques

Michael A. Trick
Sun Jun 14 12:49:07 EDT 1998