Generating Cutting Planes for Pure BIP

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

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more