Mixed-integer cuts: Difference between revisions

Revision as of 22:39, 12 December 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 linear programming problems in order to make the extreme points of the feasible region be integers as opposed to points with fractional values. Extreme points are the points of intersection between two limiting equations or cuts. 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.

Mixed-Integer Process

Mixed-integer programs (MIP) are difficult for machines to compute without more precise constraints, so the process for solving MIP is to first relax the constraints of the problem so that fractional units are allowed as in Linear Programming (LP) and then partition the problem into sub-problems (3). These sub-problems are determined by the cuts made to the feasible solution. The process to create cuts is to shrink the feasible region of the problem through additional constraints such that the extreme points of interest in the feasible region are the closest integers to the edges of the LP relaxed feasible region.

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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} }

The Gomory cut is defined as:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 non-integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i^* } constraint:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j}a_{i,j}^*x_j=b_i^* }

3. Rewrite constraint using fractional parts Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] } :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j }

4. Add new constraintFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j}f_{i,j}x_j-f_j\geq0 } , with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i^* } 's are integers.

Example:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}}

Cut:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}}

Cut:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}}

Cover Cuts

The feasible region of a knapsack problem can be reduced using minimal cover inequalities. The short coming of the cut is that it does not reflect the weights of each item in the knapsack problem because the coefficients of the inequalities derived from the knapsack problem are fixed to 1 (2).

For a given knapsack inequality:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} }

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C\subset J} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j\in C} a_j > b}

The cover inequality is:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}}

Example:

Change numbers

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24}

Some minimal cover inequalities of Z are:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1+x_2+x_4 \leq 2}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1+x_3+x_4 \leq 2}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1+x_4+x_6 \leq 2}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2+x_3+x_4+x_6 \leq 3}

Numerical Example

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max f = x_1 + x_2 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s.t. \quad 3x_1 +2x_2 \leq 5 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \qquad \quad x_2 \leq 2 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \qquad \quad x_1,x_2 \geq 0 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \qquad \quad x_2\in Z }

Convert to Standard Form:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max f = x_1 + x_2 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s.t. \quad 3x_1 + 2x_2 +s_1 = 5 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \qquad \quad x_2 +s_2 =2 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \qquad \quad x_1,x_2,s_1,s_2 \geq 0 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \qquad \quad x_2 \in Z }

Initial Basic Feasible Solution:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_1 = 5, s_2 = 2 }

Simplex Tabeau Iteration 1
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_B}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_B}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_B}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_2}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_3}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_4}
0	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_3}	5	3	2	1	0
0	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_4}	2	0	1	0	1

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_j = [ 1 \quad 1 \quad 0 \quad 0]}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_j = [ 0 \quad 0 \quad 0 \quad 0] }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0] }

Applications

Mixed-Integer Linear Programming is used in areas where fractional amounts are not practical or just impossible such as production planning, airline scheduling, network design, and combinatorial auctions (3).

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. Balas, E., et al. “Gomory Cuts Revisited.” Operations Research Letters, vol. 19, no. 1, July 1996, pp. 1–9., doi:10.1016/0167-6377(96)00007-7.

2. Weismantel, Robert. “On the 0/1 Knapsack Polytope.” Mathematical Programming, vol. 77, no. 3, 1997, pp. 49–68., doi:10.1007/bf02614517.

3. Günlük, Oktay. "Cutting Planes for Mixed-Integer Programming:Theory and Practice". Math Sciences, IBM Research. April 2018, pp. 1-4, http://www.princeton.edu/~aaa/Public/Teaching/ORF523/ORF523_Lec17_guest.pdf

@@ Line 130: / Line 130: @@
 <math>s_1 = 5, s_2 = 2
 </math>
+{| class="wikitable"
-Simplex Tabeau Iteration 1:
+|+Simplex Tabeau Iteration 1
+!<math>C_B</math>
-<math>C_B \quad Y_B \quad X_B \quad  y_1 \quad y_2 \quad y_3 \quad y_4
+!<math>Y_B</math>
-</math>
+!<math>X_B</math>
+!<math>y_1</math>
-<math>0 \quad y_3 \quad 5 \quad 3\quad 2 \quad 1\quad 0
+!<math>y_2</math>
-</math>
+!<math>y_3</math>
+!<math>y_4</math>
-<math>0 \quad y_4 \quad 2 \quad 0 \quad 1\quad0 \quad 1
+|-
-</math>
+|0
+|<math>y_3</math>
+|5
+|3
+|2
+|1
+|0
+|-
+|0
+|<math>y_4</math>
+|2
+|0
+|1
+|0
+|1
+|}
+<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>
 <math>f_j = [ 0 \quad 0 \quad 0 \quad 0]
@@ Line 153: / Line 169: @@
 ==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==
 . Balas, E., et al. “Gomory Cuts Revisited.” ''Operations Research Letters'', vol. 19, no. 1, July 1996, pp. 1–9., doi:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 10.1016/0167-6377(96)00007-7].