Mixed-integer cuts: Difference between revisions
No edit summary |
(Added image for cutting planes and edited intro) |
||
Line 2: | Line 2: | ||
== Introduction == | == Introduction == | ||
In mixed-integer programming, mixed-integer cuts are additional constraints placed upon | 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. | ||
== Cutting Planes == | == 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 | The process to create cuts is to first take the mixed-integer problem and then relax the variables to a linear programming problem (LP relaxing) and 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. | ||
[[File:Convex hull.jpg|alt=Convex hull in an LP relaxed problem|thumb|251x251px|In the photo above, the feasible region of an LP relaxed problem is shown in yellow while the feasible region of that same problem in MILP is shown in green]] | |||
== Gomory Cuts == | == 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). | Ralph Gomory sought out to solve mixed integer linear programming problems by using cutting planes in the late fifties and early sixties (1). |
Revision as of 13:33, 22 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 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.
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 (LP relaxing) and 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:
The Gomory cut is defined as:
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 constraint:
3. Rewrite constraint using fractional parts :
4. Add new constraint, with integer excess, to tableau.
5. Repeat steps 2-4 until all right hand side 's are integers.
Example:
Cut:
Cut:
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:
Let and
The cover inequality is:
Example:
Change numbers
Some minimal cover inequalities of Z are:
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. 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.