Mixed-integer cuts: Difference between revisions
m (Added intro) |
m (Added section for cutting planes) |
||
| Line 3: | Line 3: | ||
== Introduction == | == 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. | 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. | |||
Revision as of 23:19, 11 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.