Operations Research Models and Methods / Methods / Integer Programming /

 Cutting Planes

 Contents The examples for this section are in the Teach IP demo (teachpdem.xls). To solve or change the model you must have the Teach IP add-in loaded. Use the Relink buttons command to establish links to the worksheet buttons.

Problem Definition

The cutting plane exercise starts when the student clicks on the Cutting Planes item on the OR/MS menu. The problem definition dialog is the same as for Branch and Bound except that the Integer Variables field is disabled. The cutting plane method described here only works for pure integer problems. There is no need to specify the number of integer variables, since it must be the same as the number of variables.

The program presents a possible name for the problem in the Name field such as TeachIP1. There can be multiple IP models in a workbook, and the integer number at the end of the name will advance as IP models are added. For the example problem we substitute the name Cut1 in the name field. The name is used as prefix for a number of named ranges on the worksheet, so once the name is specified it should not be changed. Names must obey the Excel rules for naming ranges. The name should begin with a letter, and include no spaces or punctuation marks (a period is OK). The underline symbol may be used and is often handy for two-part names such as P_1. The name P1 won't work because it resembles a cell reference.

Other fields specify the number of variables and number of constraints. The maximum number of variables is 20 and the maximum number of constraints is 10. The model must be expressed as a maximization. If the Make Random Problem box is checked, the program provides random coefficients for the objective function and constraints. Random problems have only less than or equal to constraints. All coefficients are integer and positive. A random problem will always have a feasible solution. When the model is displayed the student can change any of the coefficients.

One of four modes of operation is chosen with a button in the Solution Options frame.

• Demonstration Option: In this mode, the program takes the student through the steps of the procedure. Message boxes describe the steps as they occur. The student presses OK buttons to progress.
• Instruction Option: In this mode, the student makes decisions on which of the several cuts available is to be added to the model. A Hint button is available which indicates the possible selections. Errors that would cause the algorithm to go astray are not allowed.
• Do it Yourself Option: Here the Hint button is disabled and the student must make all the decisions directing the algorithm.
• Run without Stopping Option: The program runs the procedure with no student interaction. The approximate delay between steps is set in the Delay field. The delay must be an integer number of seconds.

Except when the programming is running under the "without stopping" option, the student is allowed to switch between options.

Example Problem

The add-in builds the model structure shown below. Data has already been entered for the example used for this section (we use the same example as for the branch and bound method). Yellow ranges are controlled by the program or contain formulas. These areas should not be changed by the student. In contrast to the branch and bound approach, the cutting plane algorithm requires that all constraint coefficients be integer.

 The format of the display follows that of other mathematical programming add-ins in the collection. The model is linear, and the linear objective coefficients of the variables are placed in the range G9:L9. Although ranges are provided for simple lower bounds( G10:L10) and simple upper bounds (G11:L11), the default values or 0 and 9999 should not be changed. This implementation of the cut procedure does not allow finite upper limits for the variables (9999 represents infinity), and the algorithm assumes lower bounds are 0. The constraint information starts in row 15. The range G15:L18 holds the linear constraint coefficients. The constraint coefficients must be integer. Each constraint has both lower and upper bounds. The lower bounds are in the column range E15:E18, and the upper bounds are in the column range F15:F18. The constraint bounds must also be integer for this method. The range D15:D18 holds the constraint values computed for the current solution. The range in column B, B2:B8 holds information required by the program and should not be changed by the student. Starting the Procedure Pressing on the Start Cut button solves the linear programming (LP) relaxation of the integer problem, that is, the integrality restrictions are dropped. As we will see, the cutting plane procedure always solves the LP relaxation, however, as the algorithm progresses new constraints are added, called cuts. These cuts eliminate parts of the feasible region that do not contain integer solutions. Finally, after a number of cuts are added, we hope that the solution to the LP will be integer. Some cut selections guarantee that an integer solution will be reached, while others do not.

 The solution to the first linear programming relaxation is shown in the figure above. Colors are used to emphasize features of the solution. The light green in the variable value range indicates nonzero variables. Light green in the constraint value range indicates loose constraints, while red shows tight constraints. Violated constraints are indicated by dark yellow in the constraint value range. Gomery Cut To the right of the constraint display we see an area labeled Gomery Cuts. That region is shown below in its entirety. Gomery cuts are derived from the linear programming solution. The procedure for deriving them is found in Chapter XXX of the text book, so we will not repeat it. We observe however, that the cuts involve the nonbasic variables of the LP solution. The indices of the nonbasic variables are placed above the yellow area in row 14. To interpret the variable indices note that the original problem has six structural variables. These are indexed 1 through 6. The problem has four less than or equal to constraints. The slack variables for the constraints are numbered successively with indices greater than the structural variables. Thus the slack variable indices for constraints Con1, Con2, Con3 and Con4 are 7, 8, 9 and 10 respectively. The procedure adds a single cut constraint at each iteration. The cut will have a slack variable that is assigned the next integer index. For example, the slack variable for the first cut will be indexed 11..

 A cut can be created for each basic variable of of the model that does not have an integer value. In the case of the example, the basic variables are X2, X5, X6, and X8, and all have fractional values, so four Gomery constraints are created. The constraint at the bottom of the list is called a Dantzig cut. We will describe that cut later, although we will not use it in this example. To illustrate the meaning of the table, consider cut C2. Row C2 happens to be the simplex row whose basic variable is X8. With the Gomery cut presentation as it is, it is difficult to determine the basic variable that corresponds to each row. The constraint in algebraic form with the constant on the right is shown below.

Every integer solution of the original model must satisfy this constraint. Clearly, the current LP solution violates the constraint because all the slack variables are zero in the current solution. We will add this constraint to the LP model and solve the problem again.

Before continuing the process we note that there are five valid cut constraints available, the four Gomery cuts and one Dantzig cut. We could in fact add one or all of them to the LP. We have chosen in the implementation to add only one. There are several heuristics to choose the cut to add. In these demonstrations, the program uses the Gomery constraint with the greatest constant value. For the example, this is C2.

The chosen Gomery cut can be added directly to the set of constraints because it involves only structural or slack variables of the problem. We go one step further however, and express the cut entirely in terms of the original structural variables. This is possible because very slack variable can be written as a function of the structural variables. For the example, the constraints C1, C3 and C4 are tight, so the slack variables for these constraints, X7, X9, and X10, are nonbasic. To illustrate we write constraint C1 with the slack variable X7 added to obtain the equality form. In the second line the equation is solved for X7.

In a similar manner, each slack variable is expressed as a function of the structural variables. These expressions are then substituted for the slack variables in the Gomery cut. The equivalents of the cut constraints are shown on the worksheet to the right of the Gomery cuts. The figure below shows the five cut constraints for the example.

Continuing the example we rewrite C2 in algebraic form. We have multiplied the inequality by -1 to obtain positive coefficients and we have placed the constant term on the right side of the inequality.

We add this constraint to the original problem. The LP model with the new constraint is shown below. Note that we add the cut to the top of the constraint matrix. We do this to emphasize the cut constraints. As we progress, each new constraint will be added to the top. The LP solution shows that the new cut is indeed a tight constraint. The solution value is smaller than the original relaxed objective function. This must be true because the cut constraint makes the former solution infeasible.

 A little later on this page we present the complete sequence of cut additions. As a preview, we show the complete model after all cuts have been added. The procedure adds seven Gomery cuts and the process finishes with the optimal integer solution.

 At the top of the worksheet in column P we have a cell that will holds the number of cuts currently added to the LP. In row 3 we will keep a record of the objective function as cuts are added. As the iterations progress these will be placed to the right of column P. The figure below shows the objective values for all seven cuts. As expected the objective decrease as cuts are added.

Dantzig Cut

The Dantzig cut is based on the requirement that at least one of the slack variables must be a nonzero integer for an integer solution to the original problem. This follows from the observation that the current solution is not integer, so the sum of the slacks must be nonzero. Since all constraints have integer coefficients, the smallest nonzero value is 1. The Dantzig cut taken from the first LP solution is written in algebraic form below. At every iteration, a Dantzig cut will be formed by the sum of the slack variables. The cuts will differ from iteration to iteration because the set of slack variables will be different.

Demonstration

 The following links lead through the ten steps of the solution for this example problem. The figures above are repeated in the first step. Iteration 1: First LP solution. Add cut 1. Iteration 2: Add cut 2. Iteration 3: Add cut 3. Iteration 4: Add cut 4. Iteration 5: Add cut 5. Iteration 6: Add cut 6. Iteration 7: Add cut 7. Iteration 8: Optimum Integer Solution

Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors