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:

displaymath1747

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

tabular764

Let's look at the first constraint:

displaymath1748

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:

displaymath1749

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_inline1779 ; it cannot be a positive value. Therefore, we have derived the following constraint:

displaymath1750

This constraint is satisfied by every feasible integer solution to our original problem. But, in our current solution, tex2html_wrap_inline1781 and tex2html_wrap_inline1783 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:

align769

gives the constraint

displaymath1751

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

If we have a constraint

displaymath1752

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

displaymath1753

to get the cut

displaymath1754

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
Tue Sep 24 10:47:49 EDT 1996