Mixed-integer cuts: Difference between revisions
No edit summary |
No edit summary |
||
Line 42: | Line 42: | ||
5. Repeat steps 2-4 until all right hand side <math> | 5. Repeat steps 2-4 until all right hand side <math> | ||
b_i^* </math>'s are integers. | b_i^* </math>'s are integers. | ||
Example: | Example: | ||
3 | <math>3 x_1 + 3\frac{2}{5} x_2 - \frac{2}{5} x_3 = 8 \frac{3}{4}</math> | ||
Cut: | Cut: | ||
2 | <math>\frac{2}{5} x_2 + \frac{3}{5} x_3 \geq \frac{3}{4}</math> | ||
-3 1 | |||
<math>-3 \frac{1}{4} x_1 + \frac{2}{5} x_2 - \frac{2}{5} x_3 = 7 \frac{5}{6}</math> | |||
Cut: | Cut: | ||
3 | <math>\frac{3}{4} x_1 + \frac{2}{5} x_2 + \frac{3}{5} x_3 \geq \frac{5}{6}</math> | ||
Line 75: | Line 78: | ||
Change numbers | Change numbers | ||
Maximize Z = 11x1+6x2+6x3+5x4+5x5+4x6+x7<=19 | Maximize Z = 11x1+6x2+6x3+5x4+5x5+4x6+x7<=19<math>\max Z = 11 x_1 + 6 x_2 + 6x_3 + 5x_4 + 5x_5 + 4x_6 + x_7 \leq 19</math> | ||
Some minimal cover inequalities of Z are: | Some minimal cover inequalities of Z are: |
Revision as of 23:33, 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:
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 + 3\frac{2}{5} x_2 - \frac{2}{5} x_3 = 8 \frac{3}{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{2}{5} x_2 + \frac{3}{5} x_3 \geq \frac{3}{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{1}{4} x_1 + \frac{2}{5} x_2 - \frac{2}{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{3}{4} x_1 + \frac{2}{5} x_2 + \frac{3}{5} x_3 \geq \frac{5}{6}}
Cover Cuts
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
Maximize Z = 11x1+6x2+6x3+5x4+5x5+4x6+x7<=19Failed 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 = 11 x_1 + 6 x_2 + 6x_3 + 5x_4 + 5x_5 + 4x_6 + x_7 \leq 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