Course 13: The Method of Solving Integer Program: Cutting Plane Method

Author: OptimizationCity Group

Table of Contents

Introduction

The main difference between an integer program and a linear program is the assumption that the variables of the problem are integer. At first glance, this assumption helps to achieve the optimal solution by controlling the all solution and report the best one as the optimal solution. Suppose a model has n binary variables (it can take zero or one value). If n=10, the number of solutions will be more than 1000. If n=20, the number of solutions will be more than one million. If n=30, the number of solutions will be more than one billion, and even the fastest computers will not be able to check all the solutions. . Now, if the number of variables is on the scale of millions, the difficulty of the solution increases rapidly.

The computational complexity of an integer program depends on two factors:

1) Number of integer variables

2) Structure of the problem

As can be seen, the number of constraints has no effect on the difficulty of solving the problem, which is contrary to the linear program. Since solving integer program is actually much more difficult than solving linear program, it sometimes seems logical to turn the problem into a relaxed linear program by removing integrity and then solving it by the simplex method. Then the solution obtained from the simplex method is rounded to integer numbers. This method may be used to solve some problems where the value of the variables is very large. But this method has the following two problems:

1- Maybe the rounded solution is no longer feasible.

2- Maybe the rounded solution is no longer optimal.

To explain the above two points, consider the following example.

The optimal solution of the above problem is x₁=2, x₂=5/9, z=11. We round the variable that has an non integer value, i.e. x₂=5/9 to the integer number x₂=1. The resulting solution is x₁=2, x₂=1 and z=7. The optimal solution of the original model, i.e. x₁=0, x₂=0, z= 10, has a lot of difference.

The most common algorithm for solving integer programming problems is the Cutting plane method. In the following, this method is studied.

Cutting plane method

Consider the following integer linear program:

The idea of the cutting plane method is to add new constraints to the corresponding linear programming problem in order to eliminate non-integer optimal solution without removing the integer solution of region S. To do this, we relax integerity condition from S and then add new constraints of the form āx=ƃ to remove the non-integer optimal solutions. Thus we have:

Example: Consider the following model:

By adding the constraints x₁≤3 and x₁+x₂≤4 to the original model and solving without integrity condition, we will reach the same solution as the integer programming model. The graphical solution of the above model is as follows.

The general form of a cut

Consider the following linear model:

Suppose that x_B is a basic feasible solution (not necessarily optimal), that is:

And also for non-basic solutions we have: x_j=0. By multiplying h≠0 in relation (2), we have:

Since x_j≥0 and ⌊a⌋≤a, then we have:

Therefore, we will have:

Since the left side of the above relation is integer, it can be written as follows:

On the other hand, by multiplying relation (2) by ⌊h⌋ and subtracting from the above relation, we have:

The above relationship is the base of many cuts that differ according to how h is chosen.

Fractional cuts or Gomory cuts

Consider h=1 in this section. In this case, relation (3) becomes as follows:

Suppose

And

which is the fractional part ā_ij , in this case:

x_B_i can be rewritten as:

Considering that x_B_i and

are integers, so s_i will also be integer.

The important property of cut (4) is that if f_i0 > 0, by adding cut (4), the non-integer optimal solution of the relaxed integer model is removed.

Note: Cut (4) can be easily added to the simplex table with the base variable S, and considering that the optimality condition remains unchanged, the only feasibility condition for the new constraint is violated. Here it can be solved by the dual simplex method.

Note: Cut (4) can be written not only for the coefficients of the constraints, but also for the coefficients of the objective function.

Note: based on adding the number of cut (4) and using the dual simplex method, an algorithm can be presented to solve the integer program. Of course, there is no reason why the number of iterations of this algorithm is finite.

Note: To select the row by which the cut is obtained, there are different innovative methods as follows:

Cases (2) and (3) are based on the elimination of the largest non-integer region and case (4) is based on the maximum reduction of the objective function.

Note: There is no reason to prefer one of the four methods over another method.

Note: There is no need to keep all the cuts in using the dual simplex method. A cut whose basic variable is at the base and the coefficient of all its variables is zero can be removed from the simplex table.

Note: Due to the errors caused by rounding, this method cannot be used for real size examples.

Example: Solve the following integer model using the goromy cuts method.

Solution: The extended form of the above model is as follows:

First, we get the final simplex table:

Fractional cuts based on the final simplex table are as follows:

Cut for row 0 (objective function):

Cut for row 1:

Cut for row 2:

You can use the 4 principles mentioned earlier to choose the cut. Assuming the principle (1) is used, cut number 3 is used.

By adding the above cut to the simplex table, the optimal solution is obtained as follows.

As can be seen, we reached the optimal solution by one iteration. Due to the fact that this model has only 2 variables, it can be solved by graphical method. To solve graphically, all cuts should be taken in terms of x₁ and x₂.

Cuts 1 and 2:

Cut 3:

By adding the above cuts, the solution (0,5) will be the optimal solution of the problem. As can be seen from the figure above, these cuts do not remove any integer solution from the set of possible solution.

Dual-All-Integer cut

In the methods of fractional cuts, in each iteration, we maintained the conditions of feasibility and optimality and sought to establish the condition of integrity. The problem of this method is the errors caused by rounding. To solve this issue, we maintain the condition of optimality (feasibility of dual problem) and integerity in each iteration and seeks to establish the feasibility condition. If the solution is infeasible, we add a cut to the problem that removes the infeasible integer solution and reduces the infeasiblity. To maintain the optimality and integrity of, you can do the following.

Maintaining the optimality: To do this, it is enough to use the dual simplex method.
Maintaining the integerity: To do this, it is enough to perform the pivote operation on the cofficient -1. For this purpose, we can use the special cut presented in the following:

Suppose that there is an initial basic solution with integer value in the table and this basic solution has optimality conditions but is not feasible (b<0). By choosing the appropriate h (0<h<1) from the general cut in the following form, we can create a cut to eliminate this infeasible solution:

For 0<h<1, cut (*) is as follows (⌊h⌋=0):

By adding the slack variable s, we have:

Note that if all ƃr≥0, the current solution is optimal, so there exists an r that:

Therefore, when this cut with basic variable s is added to the simplex table, s removes from the base in the dual simplex method. To enter x_k to the base:

First: to be a_rk <0 (according to the dual simplex method)

Second: to maintain the integrity condition of the solution, h should be chosen in such a way that we have:

Third: the new c̄_j after the pivote operation is as follows:

For a_rj<0 and h>0, we have:

Therefore, a necessary condition to maintain the optimality condition is:

It was mentioned that to choose h, the following condition must first be met:

Therefore:

To meet optimality condition, we have the following for the value of h:

If c̄_k =0, any value of h can be chosen:

If c̄_k >0 it is enough to have:

So h should be in the following range:

Note: For any value h≤h* the conditions of optimality and integrity will be maintained, but it is better to choose h=h* to increase the changes of the objective function.

Note: In the simplex table, the cut where the value of slack variable in the base is positive and the rest of the variables are zero can be removed.

Note: To create this type of cuts, there must be a basic solution with integer value that satisfies the optimality condition. Such a basis can be easily derived. For this purpose, consider the following model:

By adding x_s as a slack variable, we can get a integer basic solution as x=0, x_s=b.

If this basic solution does not apply in optimal condition (that is, for a variable such as k, you have c_k<0), we can add a constraint in the following form (assuming the problem is bounded), where M is a large number:

Then x_k with the lowest c_k is entered into the base and s is removed from the base. This is done by pivoting on the coefficient +1 to maintain both the integrity and optimality condition.

The algorithm of Dual-All-Integer Cut is as follows: we start with an infeasible integer basic solution for the dual simplex method. To remove the infeasible solution, we add the integer cut to the table till reach the optimal solution for the main problem.

Example: Solve the following integer programming model using dual-all-integer cut.

Solution: The extensive form of the above model is as follows:

To obtain a integer basic soluton in which the optimal condition is satisfied, the following constraint can be used:

But the constraint x₁+x₂+x₃=6 is in this form and there is no need to add the above constraint. In other words, it is enough to remove the variable x₃ from the base and enter the variable x₂ (the lowest coefficient in the standard form of the simplex table) to the base.

It can be seen that we have reached a integer basic solutoin by having the optimality condition. Because -9 is negative, we make the cut with row 2. Also:

Therefore, variable x₁ enters the base. To calculate h* we have:

Therefore, the cut is defined as follows:

We add the above cut to the simplex table.

Considering that we reached an infeasible solution, a new cut must be added:

And finally we reach the optimal solution.

Primal-All-Integer cut

By using the simplex method, integer program can be solved in another way. It is maintaining the conditions of integrity and feasibility; and establishing the condition of optimality. To maintain the feasibility, it is sufficient to use the ratio test to maintain the basic feasibility with the prim simplex method. To maintain the integrity, it is enough to perform the pivoting operation on +1. If the optimality condition is satisfied in the simplex table (c_j≥0), the problem is solved. Suppose c_k<0 and x_k is the input variable to the base and x_r is the output variable from the base, which is obtained from the following test.

By entering x_k instead of x_r in the base, the feasibility condition will remain. Now, if ā_rk=1, the condition of integrity will remain. Suppose ā_rk>1 , then:

And therefore, the general cut is as follows:

According to the above cut, the Primal-All-Integer cut algorithm for can be expressed as follows.

We start with a integer feasible solution. if it is not optimal we add a cut to move towards another integer feasible solution with a better objective function.

Example: Solve the following model by the method of primal-all-integer cut.

Solution: The extensive form of the above model is as follows:

First cut:

Second cut:

Third cut:

Example: Consider the following integer programming model.

a) Solve the above model by adding Fractional cut (Gomory cut).

b) Solve the above model by adding Primal-All-Integer cut.

c) Solve the above model by adding Dual-All-Integer cut

Solution:

The extensive form of the above model is as follows:

Fractional cut

First cut:

In order to choose the best cut to add to the simplex table, we use the principles presented in the lesson. According to principle 1, cut 3 is chosen to be added to the simplex table. By adding the above cut to the simplex table, the results are as follows.

Second cut:

All the above cuts are one cut, so we add the following cut:

By adding the above cut, the simplex table becomes as follows.

Third cut:

All the above cuts are one cut, so we add the following cut:

By adding the above cut, the simplex table becomes as follows.

The optimal solution is obtained from the last table, which is x=(3,1) and z=7.

b) Solving by the method of Primal-All-Integer cut

First cut:

Second cut:

Third cut:

The optimal solution is obtained from the last table, which is x=(3,1) and z=7.

c) Solving by Dual-All-Integer cut

In order to obtain an integer basic solution in which the optimality condition is satisfied, the following constraints can be added:

Since the first constraint is in this form, there is no need to add the above constraint. Therefore, variable x₃ is removed from the base and variable x₁ (which has the lowest coefficient in the objective function) enters the base. The calculations are shown in the figure below.

It can be seen that we have an infeasible basic solution having integrity and optimality. Because -9<0, so we make the cut for row 3.

The cut is as follows.

By adding the above cut in the simplex table, we have

Due to the fact that -1<0, a cut is made for row 2. Since x₃ has the negative coefficient value among the non-basic variables in row 2, this variable enters the basis. To calculate h* we have

In the table below, the above cut is added to the constraints.

In the above table, an optimal solution having integrity and feasiblity is obtained. Therefore, the process of adding the cut is stopped. The optimal solution is x=(3,1) and z=7.

Example:

Consider the following integer programming model.

a) Solve the above model by adding Fractional cut (Gomory cut).

b) Solve the above model by adding Dual-All-Integer cut

Solution:

The extensive form of the above model is as follows.

Among the three cuts above, the first cut is selected.

By adding the above cut, we will have.

Based on the table above, for rows 2 and 3, the fractional cut can be generated.

Both cuts are the same. Therefore, the following cut is added to the simplex table.

To obtain a integer and optimal basis, the following constraint can be used.

The variable x₇ leaves the base and x₂ enters the base (due to the lowest value of the coefficient of the objective function).

It can be seen that an optimal and integer base is obtained. Therefore, for row 2, we make a cut and since x₁ has the lowest coefficient in the objective function, x₁ enters the base.