Mixed-integer cuts

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Revision as of 21:34, 13 December 2020 by Pwg48 (talk | contribs)
Jump to navigation Jump to search

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 (3).

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.

Convex hull in an LP relaxed problem
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

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:

Flow Cover 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 0 \leq d - \sum_{j \in C+}x_j - \sum_{j \in C++}(m_j - λ(1-y_j) } Where Failed to parse (syntax error): {\displaystyle λ = \sum_{j \in C+} m_j - d > 0 <\math> and <math> C++ = \{j \in C+ : m_j > λ\} == Numerical Example== <math>\max f = x_1 + x_2 }

Convert to Standard Form:

Initial Basic Feasible Solution:

Simplex Tableau Iteration 1
0 5 3 2 1 0
0 2 0 1 0 1

Optimal solution not found

leaves the basis

Simplex Tableau Iteration 2

1 1 0
0 2 0 1 0 1

Optimal Solution not found

leaves the basis

Simplex Tableau Iteration 3

1 1 0
1 2 0 1 0 1

Optimal Solution found:

is not an integer Fractional part of is Fractional part of is 0

Gomory Cut will be made from of the Simplex Tableau

Let Rewritten as

Simplex Tableau Iteration 4

1 1 0 0
1 2 0 1 0 1 0
0 0 0 1


Solution found, however the basic variable is negative. The solution is infeasible. leaves the basis

enters the basis

Simplex Tableau Iteration 5

1 0 1 0 0 -1 1
1 2 0 1 0 1 0
0 1 0 0 1 1 -3

Optimal Solution found

Applications

Mixed-Integer Linear Programming is used in areas where fractional amounts are not practical or even impossible such as labor distribution, scheduling, and purchasing additional equipment. Many of these MILP methods utilize one of the many mixed-integer cut methods to find integer solutions from relaxed linear constraints as seen with the Bender decomposition (6). The distribution process through mixed-integer programming allows for more flexible and quicker schedules (4). MILP in scheduling for teachers allows administrators to manage each teacher's load and match a class's needs to the teacher's abilities (5).

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. Balas, Egon. (1985). Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems. December, 1983. 38 pp. 2-3, doi:[1].

4. Rave, Jorge Iván Perez, & Álvarez, Gloria Patricia Jaramillo. (2011). Application of mixed-integer linear programming in a car seats assembling process. Pesquisa Operacional, 31(3), pp. 593-610. doi: [2]

5. Qu, Xiaobo & Yi, Wen &Wang, Tingsong &Wang, Shuaian &Aiao, Lin & Liu, Zhiyuan. (2017). Mixed-Integer Linear Programming Models for Teaching Assistant Assignment and Extensions. January 2017. Scientific Programming. pp. 1-4. doi: [3]

6. Lindsay Siegmundt, Peter Haddad, Chris Babbington, Jon Boisvert, Haris Shaikh. (2020). Branch and cut. December 2020. doi:[4]/index.php?title=Branch_and_cut