Mixed-integer cuts: Difference between revisions

Revision as of 18:31, 21 November 2020

Author: Ryan Carr, Patrick Guerrette, Mark James (SysEn 5800 Fall 2020)

Introduction

In mixed-integer programming, mixed-integer cuts are additional constraints placed upon the problem in order to make the extreme points of the feasible region be integers as opposed to points with fractional values. These cuts reduce the feasible region, making the problem easier to solve. A mixed-integer problem can be reduced with mixed-integer cuts until its feasible region reaches the convex hull, where all extreme points of the feasible region are integers.

Cutting Planes

The process to create cuts is to first take the mixed-integer problem and then relax the variables to a linear programming problem and tighten the problem through additional constraints such that extreme points of the feasible region are integers.

Gomory Cuts

Ralph Gomory sought out to solve mixed integer linear programming problems by using cutting planes in the late fifties and early sixties [1].

For a given knapsack inequality:

$\sum _{j}a_{i,j}x_{j}\leq b_{i}\qquad x_{j}\in \{0,1\}$

The gomory cut is defined as:

$\sum _{j}\lfloor a_{i,j}\rfloor x_{j}\leq \lfloor b_{i}\rfloor$

Using the simplex method with gomory cuts(fractional example):

1. Begin with LP in standard form for application of simplex method.

2. Apply simplex method until convergence, and select any noninteger $b_{i}^{*}$ constraint:

$\sum _{j}a_{i,j}^{*}x_{j}=b_{i}^{*}$

3. Rewrite constraint using fractional parts $f_{i,j}=a_{i,j}-[a_{i,j}],\quad f_{i}=b_{i}-[b_{i}]$ :

$\sum _{j}f_{i,j}^{*}x_{j}-f_{j}^{*}=b_{j}^{*}=[b_{j}^{*}]-\sum _{j}[a_{i,j}^{*}]x_{j}$

4. Add new constraint $\sum _{j}f_{i,j}x_{j}-f_{j}\geq 0$ , with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand sideFailed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. TeX parse error: Prime causes double exponent: use braces to clarify"): {\displaystyle b_{i}^{*}'s} are integers.

Example:

3 x1 + 3 2/5 x2 - 2/5 x3= 8 ¾

Cut:

2/5 x2 + 3/5 x3 >= ¾

-3 1/4 x1 + 2/5 x2 - 2/5 x3= 7 ⅚

Cut:

3/4 x1 + 2/5 x2 + 3/5 x3 >= 5/6

Cover Cuts

For a given knapsack inequality:

jaijxjbi xj{0,1}

Let CJ and jCaj>b

The cover inequality is:

jCxjC-1, xj{0,1}

Example:

Change numbers

Maximize Z = 11x1+6x2+6x3+5x4+5x5+4x6+x7<=19

Some minimal cover inequalities of Z are:

X1+x2+x3 <=2

X1+x2+x6 <=2

X1+x5+x6 <= 2

X3+x4+x5+x6 <=3

Applications

Conclusion

Mixed Integer Cuts allows for shorter computational time in solving mixed integer linear programs by refining the feasible region with linear inequalities. If the optimum found by solving the non-integer linear program is non-integer, a linear inequality can be determined to remove the solution from the feasible region leading to the convex hull.

References

[1] Gomory Cuts revisited

Mixed integer nonlinear programming

Laurence A. Wolsey - Integer Programming

@@ Line 9: / Line 9: @@
 Ralph Gomory sought out to solve mixed integer linear programming problems by using cutting planes in the late fifties and early sixties [1].
-<math>
- a_{i,j} x_j \leq b_i</math>
 For a given knapsack inequality:
-jaijxjbi    xj{0,1}
+<math>
+ \sum_{j}a_{i,j} x_j \leq b_i  \qquad  x_j \in \{0,1\}  </math>
 The gomory cut is defined as:
-j⌊aij⌋xj⌊bi⌋
+<math>
+ \sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>
 Using the simplex method with gomory cuts(fractional example):
@@ Line 24: / Line 24: @@
 . Begin with LP in standard form for application of simplex method.
-. Apply simplex method until convergence, and select any nonintegerb∗iconstraint:∑ja∗ijxj=b∗i
+. Apply simplex method until convergence, and select any noninteger <math>
+ b_i^* </math>constraint:
+<math>
+ \sum_{j}a_{i,j}^*x_j=b_i^* </math>
+. Rewrite constraint using fractional parts <math>
+ f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:
+<math>
+ \sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>
-. Rewrite constraint using fractional partsfij=aij−[aij],fi=bi−[bi]:∑jf∗ijxj−f∗j= [b∗j]−∑j[a∗ij]xj
+. Add new constraint<math>
+ \sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.
-Heuristic for step 2: chooseb∗iwith largestf∗i.
+. Repeat steps 2-4  until all right hand side<math>
+ b_i^*'s </math> are integers.
-. Add new constraint∑jfijxj−fj≥0, with integer excess, to tableau.
-. Repeat steps 2-4 (using dual simplex) until all rhsb∗i’s are integers.
+Example:
 x1 + 3 2/5 x2 - 2/5 x3= 8 ¾