Generating Cutting Planes for Pure BIP

Generating Cutting Planes for Pure BIP

A cutting plane (or cut) for any IP problem is a new functional constraint that reduces the feasible region for the LP relaxation without eliminating any feasible solutions for the IP problem. In fact, you have just seen one way of generating cutting planes for pure BIP prob- lems, namely, apply the above procedure for tightening constraints. Thus, x1 + x2 ::: 1 is a cutting plane for the BIP problem considered in Fig. 12.14, which leads to the reduced fea- sible region for the LP relaxation shown in Fig. 12.15.

In addition to this procedure, a number of other techniques have been developed for generating cutting planes that will tend to accelerate how quickly a branch-and-bound algorithm can find an optimal solution for a pure BIP problem. We will focus on just one of these techniques.

To illustrate this technique, consider the California Manufacturing Co. pure BIP prob- lem presented in Sec. 12.1 and used to illustrate the BIP branch-and-bound algorithm in Sec. 12.6. The optimal solution for its LP relaxation is given in Fig. 12.5 as (x1, x2, x3, x4) = (--, 1, 0, 1). One of the functional constraints is

This new constraint is a cutting plane. It eliminates part of the feasible region for the LP relaxation, including what had been the optimal solution, (--, 1, 0, 1), but it does not elim- inate any feasible integer solutions. Adding just this one cutting plane to the original model

would improve the performance of the BIP branch-and-bound algorithm in Sec. 12.6 (see Fig. 12.9) in two ways. First, the optimal solution for the new (tighter) LP relaxation

would be (1, 1, --, 0), with Z = 15--, so the bounds for the All node, x = 1 node, and (x1, x2) = (1, 1) node now would be 15 instead of 16. Second, one less iteration would be needed because the optimal solution for the LP relaxation at the (x1, x2, x3) = (1, 1, 0) node now would be (1, 1, 0, 0), which provides a new incumbent with Z* = 14. There- fore, on the third iteration (see Fig. 12.8), this node would be fathomed by test 3, and the (x1, x2) = (1, 0) node would be fathomed by test 1, thereby revealing that this incumbent is the optimal solution for the original BIP problem.

Here is the general procedure used to generate this cutting plane.

A Procedure for Generating Cutting Planes

1. Consider any functional constraint in ::: form with only nonnegative coefficients.

2. Find a group of variables (called a minimum cover of the constraint) such that

(a) The constraint is violated if every variable in the group equals 1 and all other vari- ables equal 0.

(b) But the constraint becomes satisfied if the value of any one of these variables is changed from 1 to 0.

3. By letting N denote the number of variables in the group, the resulting cutting plane has the form

Sum of variables in group ::: N - 1.

Applying this procedure to the constraint 6x1 + 3x2 + 5x3 + 2x4 ::: 10, we see that the group of variables {x1, x2, x4} is a minimal cover because

(a) (1, 1, 0, 1) violates the constraint.

(b) But the constraint becomes satisfied if the value of any one of these three vari- ables is changed from 1 to 0.

Since N = 3 in this case, the resulting cutting plane is x1 + x2 + x4 ::: 2.

This same constraint also has a second minimal cover {x1, x3}, since (1, 0, 1, 0) violates the constraint but both (0, 0, 1, 0) and (1, 0, 0, 0) satisfy the constraint. There-fore, x1 + x3 ::: 1 is another valid cutting plane.

The branch-and-cut approach involves generating many cutting planes in a similar manner before then applying clever branch-and-bound techniques. The results of in- cluding the cutting planes can be quite dramatic in tightening the LP relaxations. In some cases, the gap between Z for the optimal solution for the LP relaxation of the whole BIP problem and Z for this problem’s optimal solution is reduced by as much as 98 percent.

Ironically, the very first algorithms developed for integer programming, including Ralph Gomory’s celebrated algorithm announced in 1958, were based on cutting planes (generated in a different way), but this approach proved to be unsatisfactory in practice (except for special classes of problems). However, these algorithms relied solely on cut- ting planes. We now know that judiciously combining cutting planes and branch-and-bound techniques (along with automatic problem preprocessing) provides a powerful algorithmic approach for solving large-scale BIP problems. This is one reason that the name branch- and-cut algorithm has been given to this approach.