Cornell University Computational Optimization Open Textbook - Optimization Wiki - User contributions [en]

Mixed-integer cuts

2020-12-14T03:07:14Z

Pwg48: /* Numerical Example */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>

== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derived by Padberg, Van Roy, and Wolsey (7).

Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>

The <math> x </math> variables are flows that are constrained by the conservation inequality with demand for <math> d</math> and upper bound constraints, where <math> m_j </math> is the capacity of <math>j</math> and <math> y_j </math> is a binary variable that determing if <math> j </math> is open (7).

The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>
== Mixed Integer Rounding Cuts==
Mixed-Integer Rounding (MIR) cuts can be considered a generalization of the Chvatal integer rounding inequality applied to mixed integer linear programs. That is, generating valid inequalities for any mixed-integer programs (8).

<math> X^{MIR} = \{(x,y) \in R_+^1 \times Z_+^2 : a_1 y_1 + a_2 y_2 \leq b + x \} </math>
where <math> a_1,a_2 </math> and <math> b </math> are scalars with <math> b \notin Z^1 </math>

Let <math> f = b - \lfloor b \rfloor </math> and <math> f_i = a_i - \lfloor a_i \rfloor </math> for <math> i = 1,2 </math>. Suppose <math> f_1 \leq f \leq f_2 </math>
The mixed integer rounding inequality is defined as:

<math> \lfloor a_1 \rfloor y_1 + (\lfloor a_2 \rfloor + \tfrac{f_2 - f}{1 - f} )y_2 \leq \lfloor b \rfloor + \tfrac{x}{1-f} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>

<math> y_1,y_2, y_3, </math> and <math> y_4 </math> correspond to <math> x_1,x_2, s_1, </math> and <math> s_2</math>

<math> C_B </math> contains the cost associated with the basic variables.

<math> Y_B</math> contains the basic variables.

<math> X_B</math> contains the basic feasible solution.

<math> f_j - c_j \geq 0 </math> for an optimal solution.

{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

7. Gu, Zonghao, et al. “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs.” Mathematical Programming, vol. 85, no. 3, 1999, pp. 439–467., doi:10.1007/s101070050067.

8. Günlük, Oktay, and Yves Pochet. “Mixing Mixed-Integer Inequalities.” Mathematical Programming, vol. 90, no. 3, 2001, pp. 429–457., doi:10.1007/pl00011430.

Mixed-integer cuts

2020-12-14T02:59:37Z

Pwg48: /* References */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>

== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derived by Padberg, Van Roy, and Wolsey (7).

Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>

The <math> x </math> variables are flows that are constrained by the conservation inequality with demand for <math> d</math> and upper bound constraints, where <math> m_j </math> is the capacity of <math>j</math> and <math> y_j </math> is a binary variable that determing if <math> j </math> is open (7).

The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>
== Mixed Integer Rounding Cuts==
Mixed-Integer Rounding (MIR) cuts can be considered a generalization of the Chvatal integer rounding inequality applied to mixed integer linear programs. That is, generating valid inequalities for any mixed-integer programs (8).

<math> X^{MIR} = \{(x,y) \in R_+^1 \times Z_+^2 : a_1 y_1 + a_2 y_2 \leq b + x \} </math>
where <math> a_1,a_2 </math> and <math> b </math> are scalars with <math> b \notin Z^1 </math>

Let <math> f = b - \lfloor b \rfloor </math> and <math> f_i = a_i - \lfloor a_i \rfloor </math> for <math> i = 1,2 </math>. Suppose <math> f_1 \leq f \leq f_2 </math>
The mixed integer rounding inequality is defined as:

<math> \lfloor a_1 \rfloor y_1 + (\lfloor a_2 \rfloor + \tfrac{f_2 - f}{1 - f} )y_2 \leq \lfloor b \rfloor + \tfrac{x}{1-f} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

7. Gu, Zonghao, et al. “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs.” Mathematical Programming, vol. 85, no. 3, 1999, pp. 439–467., doi:10.1007/s101070050067.

8. Günlük, Oktay, and Yves Pochet. “Mixing Mixed-Integer Inequalities.” Mathematical Programming, vol. 90, no. 3, 2001, pp. 429–457., doi:10.1007/pl00011430.

Mixed-integer cuts

2020-12-14T02:58:25Z

Pwg48: /* Gomory Cuts */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>

== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derived by Padberg, Van Roy, and Wolsey (7).

Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>

The <math> x </math> variables are flows that are constrained by the conservation inequality with demand for <math> d</math> and upper bound constraints, where <math> m_j </math> is the capacity of <math>j</math> and <math> y_j </math> is a binary variable that determing if <math> j </math> is open (7).

The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>
== Mixed Integer Rounding Cuts==
Mixed-Integer Rounding (MIR) cuts can be considered a generalization of the Chvatal integer rounding inequality applied to mixed integer linear programs. That is, generating valid inequalities for any mixed-integer programs (8).

<math> X^{MIR} = \{(x,y) \in R_+^1 \times Z_+^2 : a_1 y_1 + a_2 y_2 \leq b + x \} </math>
where <math> a_1,a_2 </math> and <math> b </math> are scalars with <math> b \notin Z^1 </math>

Let <math> f = b - \lfloor b \rfloor </math> and <math> f_i = a_i - \lfloor a_i \rfloor </math> for <math> i = 1,2 </math>. Suppose <math> f_1 \leq f \leq f_2 </math>
The mixed integer rounding inequality is defined as:

<math> \lfloor a_1 \rfloor y_1 + (\lfloor a_2 \rfloor + \tfrac{f_2 - f}{1 - f} )y_2 \leq \lfloor b \rfloor + \tfrac{x}{1-f} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

7. Gu, Zonghao, et al. “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs.” Mathematical Programming, vol. 85, no. 3, 1999, pp. 439–467., doi:10.1007/s101070050067.

Mixed-integer cuts

2020-12-14T02:58:09Z

Pwg48:

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derived by Padberg, Van Roy, and Wolsey (7).

Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>

The <math> x </math> variables are flows that are constrained by the conservation inequality with demand for <math> d</math> and upper bound constraints, where <math> m_j </math> is the capacity of <math>j</math> and <math> y_j </math> is a binary variable that determing if <math> j </math> is open (7).

The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>
== Mixed Integer Rounding Cuts==
Mixed-Integer Rounding (MIR) cuts can be considered a generalization of the Chvatal integer rounding inequality applied to mixed integer linear programs. That is, generating valid inequalities for any mixed-integer programs (8).

<math> X^{MIR} = \{(x,y) \in R_+^1 \times Z_+^2 : a_1 y_1 + a_2 y_2 \leq b + x \} </math>
where <math> a_1,a_2 </math> and <math> b </math> are scalars with <math> b \notin Z^1 </math>

Let <math> f = b - \lfloor b \rfloor </math> and <math> f_i = a_i - \lfloor a_i \rfloor </math> for <math> i = 1,2 </math>. Suppose <math> f_1 \leq f \leq f_2 </math>
The mixed integer rounding inequality is defined as:

<math> \lfloor a_1 \rfloor y_1 + (\lfloor a_2 \rfloor + \tfrac{f_2 - f}{1 - f} )y_2 \leq \lfloor b \rfloor + \tfrac{x}{1-f} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

7. Gu, Zonghao, et al. “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs.” Mathematical Programming, vol. 85, no. 3, 1999, pp. 439–467., doi:10.1007/s101070050067.

Mixed-integer cuts

2020-12-14T02:19:01Z

Pwg48: /* Flow Cover Cut */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derived by Padberg, Van Roy, and Wolsey (7).

Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>

The <math> x </math> variables are flows that are constrained by the conservation inequality with demand for <math> d</math> and upper bound constraints, where <math> m_j </math> is the capacity of <math>j</math> and <math> y_j </math> is a binary variable that determing if <math> j </math> is open (7).

The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

7. Gu, Zonghao, et al. “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs.” Mathematical Programming, vol. 85, no. 3, 1999, pp. 439–467., doi:10.1007/s101070050067.

Mixed-integer cuts

2020-12-14T02:08:51Z

Pwg48: /* Flow Cover Cut */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derivced by Padberg, Van Roy, and Wolsey(7).

Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>
The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

7. Gu, Zonghao, et al. “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs.” Mathematical Programming, vol. 85, no. 3, 1999, pp. 439–467., doi:10.1007/s101070050067.

Mixed-integer cuts

2020-12-14T02:03:22Z

Pwg48: /* References */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derivced by Padberg, Van Roy, and Wolsey(7)

Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>
The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

7. Gu, Zonghao, et al. “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs.” Mathematical Programming, vol. 85, no. 3, 1999, pp. 439–467., doi:10.1007/s101070050067.

Mixed-integer cuts

2020-12-14T02:02:46Z

Pwg48: /* Flow Cover Cut */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derivced by Padberg, Van Roy, and Wolsey(7)

Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>
The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

Mixed-integer cuts

2020-12-14T02:01:35Z

Pwg48: /* Flow Cover Cut */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
Flow Cover Cuts were introduced and derivced by Padberg, Van Roy, and Wolsey [4]
Given the system
<math> X = \{(x,y) \in R_+^n \times B^n : \sum{j \in N+} x_j - \sum_{j \in N-} x_j \leq d, x_j \leq m_jy_j, j \in N \} </math>

where <math> N = N+ \cup N- </math> and <math> n = |N| </math>
The flow cover inequality is defined as:

<math> 0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}(m_j - l)(1-y_j) </math>

Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

Mixed-integer cuts

2020-12-14T01:46:53Z

Pwg48:

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==

<math>
0 \leq d - \sum_{j \in C+} x_j - \sum_{j \in C++}\(m_j - l)(1-y_j) </math>
Where <math> l = \sum_{j \in C+} m_j - d > 0 </math> and
<math> C++ = \{j \in C+ : m_j > l\} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

Mixed-integer cuts

2020-12-14T01:35:17Z

Pwg48: /* Flow Cover Cut */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
<math>
0 \leq d - \sum_{j \in C+}x_j - \sum_{j \in C++}(m_j - λ(1-y_j) </math>
Where <math> λ = \sum_{j \in C+} m_j - d > 0 <\math> and
<math> C++ = \{j \in C+ : m_j > λ\} </math>

== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

Mixed-integer cuts

2020-12-14T01:34:11Z

Pwg48:

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Flow Cover Cut==
<math>
0 \leq d - \sum_{j \in C+}x_j - \sum_{j \in C++}(m_j - λ(1-y_j) </math>
Where <math> λ = \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
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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:[https://www.researchgate.net/publication/30867666_Disjunctive_Programming_and_a_Hierarchy_of_Relaxations_for_Discrete_Optimization_Problems].

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: [http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382011000300011&lng=en&tlng=en]

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: [https://www.hindawi.com/journals/sp/2017/9057947/]

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

Mixed-integer cuts

2020-12-13T18:41:36Z

Pwg48: /* Numerical Example */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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

Mixed-integer cuts

2020-12-13T18:39:26Z

Pwg48: /* Numerical Example */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|0
|-
|1
|<math>y_4</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|0
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|0
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math> G_1
</math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} < 0 \}
</math>
<math> G_1
</math> leaves the basis

<math> \max \{ \tfrac{f_j - c_j}{y_{bi}} , y_{bj} < 0 \}</math>
<math> = \max\{-1,-1\}
</math>
<math> y_3
</math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|1
|<math>y_1</math>
|0
|1
|0
|0
| -1
|1
|-
|1
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
| -3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 </math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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

Mixed-integer cuts

2020-12-13T18:18:11Z

Pwg48: /* Numerical Example */

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.
[[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 ==
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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

The Gomory cut is defined as:

<math>
\sum_{j} \lfloor a_{i,j} \rfloor x_j \leq \lfloor b_i \rfloor </math>

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 <math>
b_i^* </math>constraint:

<math>
\sum_{j}a_{i,j}^*x_j=b_i^* </math>

3. Rewrite constraint using fractional parts <math>
f_{i,j}=a_{i,j}-[a_{i,j}], \quad f_i=b_i - [b_i] </math>:

<math>
\sum_{j}f_{i,j}^*x_j-f_j^*=b_j^*=[b_j^*]-\sum_{j}[a_{i,j}^*]x_j </math>

4. Add new constraint<math>
\sum_{j}f_{i,j}x_j-f_j\geq0 </math>, with integer excess, to tableau.

5. Repeat steps 2-4 until all right hand side <math>
b_i^* </math>'s are integers.

Example:

<math>3 x_1 + 4\frac{1}{5} x_2 - \frac{3}{5} x_3 = 8 \frac{1}{4}</math>

Cut:

<math>\frac{4}{5} x_2 + \frac{2}{5} x_3 \geq \frac{1}{4}</math>

<math>-3 \frac{3}{4} x_1 + 2 \frac{3}{5} x_2 - 1 \frac{1}{5} x_3 = 7 \frac{5}{6}</math>

Cut:

<math>\frac{1}{4} x_1 + \frac{3}{5} x_2 + \frac{4}{5} x_3 \geq \frac{5}{6}</math>
== 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:

<math>
\sum_{j}a_{i,j} x_j \leq b_i \qquad x_j \in \{0,1\} </math>

Let <math>C\subset J</math> and <math>\sum_{j\in C} a_j > b</math>

The cover inequality is:

<math>\sum_{j \in C}x_j\leq |C| - 1, \quad x_j \in \{0,1\}</math>

Example:

Change numbers

<math>\max Z = 12 x_1 + 5 x_2 + 7x_3 + 8x_4 + 3x_5 + 5x_6 + 6x_7 \leq 24</math>

Some minimal cover inequalities of Z are:

<math>x_1+x_2+x_4 \leq 2</math>

<math>x_1+x_3+x_4 \leq 2</math>

<math>x_1+x_4+x_6 \leq 2</math>

<math>x_2+x_3+x_4+x_6 \leq 3</math>
== Numerical Example==

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 +2x_2 \leq 5
</math>

<math>\qquad \quad x_2 \leq 2
</math>

<math>\qquad \quad x_1,x_2 \geq 0
</math>

<math>\qquad \quad x_1\in Z
</math>

Convert to Standard Form:

<math>\max f = x_1 + x_2
</math>

<math>s.t. \quad 3x_1 + 2x_2 +s_1 = 5
</math>

<math>\qquad \quad x_2 +s_2 =2
</math>

<math>\qquad \quad x_1,x_2,s_1,s_2 \geq 0
</math>

<math>\qquad \quad x_1 \in Z
</math>

Initial Basic Feasible Solution:

<math>s_1 = 5, s_2 = 2
</math>
{| class="wikitable"
|+Simplex Tableau Iteration 1
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</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]
</math>

<math>f_j - c_j = [ -1 \quad -1 \quad 0 \quad 0]
</math>

Optimal solution not found

<math>\min \{ \tfrac{5}{3}, \tfrac{2}{0} \}</math>

<math>y_3</math> leaves the basis

'''Simplex Tableau Iteration 2'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|0
|<math>y_1</math>
|<math>\tfrac{5}{3}</math>
|1
|<math>\tfrac{2}{3}</math>
|<math>\tfrac{1}{3}</math>
|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 = [ 1 \quad \tfrac{2}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad -\tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Optimal Solution not found

<math>\min \{ \tfrac{5}{2}, 2 \}</math>

<math>y_4</math> leaves the basis

'''Simplex Tableau Iteration 3'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
|-
|0
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|-
|0
|<math>y_2</math>
|2
|0
|1
|0
|1
|}
<math>c_j = [ 1 \quad 1 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3}]
</math>

Optimal Solution found:

<math>x_1 = \tfrac{1}{3} \quad x_2 = 2
</math>

<math>x_1
</math> is not an integer
Fractional part of <math>x_1
</math> is <math>\tfrac{1}{3}
</math>
Fractional part of <math>x_2
</math> is 0

<math>\max \tfrac{1}{3} , 0
</math>
Gomory Cut will be made from <math>y_1
</math> of the Simplex Tableau

Let <math>G_1 = -\tfrac{1}{3} + 0x_1 + 0x_2 + \tfrac{1}{3} s_1 + \tfrac{1}{3}s_2
</math>
Rewritten as
<math>-\tfrac{1}{3}s_1 - -\tfrac{1}{3}s_2 + G_1 = -\tfrac{1}{3}
</math>

'''Simplex Tableau Iteration 4'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|0
|<math>y_1</math>
|<math>\tfrac{1}{3}</math>
|1
|0
|<math>\tfrac{1}{3}</math>
|<math>-\tfrac{2}{3}</math>
|0
|-
|0
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>G_1</math>
|<math>-\tfrac{1}{3}</math>
|0
|0
|<math>-\tfrac{1}{3}</math>
|<math>-\tfrac{1}{3}</math>
|1
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 0]
</math>

Solution found, however the basic variable <math>G_1<\math> is negative.
The solution is infeasible.
<math> \min \{x_{bi},x_{bi} \l 0 \} <\math>
<math> G_1 <\math> leaves the basis
<math> \max \{\tfrac{f_j - c_j}{y_{bj},y_{bj} \l 0 \} = \max\{-1,-1} <\math>
<math> y_3 <\math> enters the basis

'''Simplex Tableau Iteration 5'''
{| class="wikitable"
!<math>C_B</math>
!<math>Y_B</math>
!<math>X_B</math>
!<math>y_1</math>
!<math>y_2</math>
!<math>y_3</math>
!<math>y_4</math>
!<math>G_1</math>
|-
|0
|<math>y_1</math>
|0
|1
|0
|0
|-1
|1
|-
|0
|<math>y_2</math>
|2
|0
|1
|0
|1
|0
|-
|0
|<math>y_3</math>
|1
|0
|0
|1
|1
|-3
|}

<math>c_j = [ 1 \quad 1 \quad 0 \quad 0 \quad 0]</math>

<math>f_j = [ 1 \quad 1 \quad \tfrac{1}{3} \quad \tfrac{1}{3} \quad 1]
</math>

<math>f_j - c_j = [ 0 \quad 0 \quad 0 \quad 0 \quad 1]
</math>

Optimal Solution found
<math> x_1 = 0, \quad x_2 = 2 <\math>

== 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:[https://www-sciencedirect-com.proxy.library.cornell.edu/science/article/pii/0167637796000077?via%3Dihub 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:[https://link.springer.com/article/10.1007/BF02614517 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

Mixed-integer cuts

2020-12-13T17:53:11Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T17:43:42Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T03:37:21Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T02:57:29Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T02:39:33Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T02:01:55Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T01:48:28Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T01:25:43Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T01:19:56Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T01:09:27Z

Pwg48: /* Numerical Example */

Mixed-integer cuts

2020-12-13T00:27:25Z

Pwg48:

Mixed-integer cuts

2020-11-22T09:30:48Z

Pwg48:

Mixed-integer cuts

2020-11-22T09:29:25Z

Pwg48:

Mixed-integer cuts

2020-11-22T09:25:51Z

Pwg48: /* References */

Mixed-integer cuts

2020-11-22T09:24:53Z

Pwg48: /* References */

Mixed-integer cuts

2020-11-22T08:23:50Z

Pwg48:

Mixed-integer cuts

2020-11-22T08:04:00Z

Pwg48:

Mixed-integer cuts

2020-11-22T06:16:44Z

Pwg48:

Mixed-integer cuts

2020-11-22T06:13:00Z

Pwg48:

Mixed-integer cuts

2020-11-22T05:28:21Z

Pwg48:

Mixed-integer cuts

2020-11-22T03:38:19Z

Pwg48:

Mixed-integer cuts

2020-11-22T03:33:44Z

Pwg48:

Mixed-integer cuts

2020-11-22T03:00:23Z

Pwg48:

Mixed-integer cuts

2020-11-21T22:33:23Z

Pwg48:

Mixed-integer cuts

2020-11-21T22:31:54Z

Pwg48:

Mixed-integer cuts

2020-11-21T21:52:03Z

Pwg48: Added Gomory Cuts, Cover Cuts, Conclusion, and References

Mixed-integer cuts

2020-11-08T18:17:46Z

Pwg48: Created page with "Author: Ryan Carr, Patrick Guerrette, Mark James (SysEn 5800 Fall 2020)"

Author: Ryan Carr, Patrick Guerrette, Mark James (SysEn 5800 Fall 2020)