# Difference between revisions of "Mixed-integer cuts"

Tahirkapoor (Talk | contribs) (Created page with "=Introduction= __TOC__ =Background= ==Gomory's Cuts=") |
Tahirkapoor (Talk | contribs) (→References) |
||

(38 intermediate revisions by one user not shown) | |||

Line 1: | Line 1: | ||

+ | Author: Tahir Kapoor (ChE 345 Spring 2015) | ||

+ | |||

+ | Stewards: Dajun Yue and Fengqi You | ||

=Introduction= | =Introduction= | ||

+ | Mixed-integer cuts or Cutting-plane methods is an iterative approach used to simplify the solution of a mixed integer linear programming (MILP) problem. Cutting-plane methods work by first relaxing the MILP to a complementary linear programming problem and cutting the feasible region to narrow down the solution search space to only include feasible solutions. Unlike the branch and bound method, which subdivides the feasible region into multiple sub-regions, mixed-integer cuts result in one feasible region which can be solved using standard linear programming methods. Proper application of mixed-integer cuts will result in a convex hull reformulation of a MILP where every extreme point of the feasible region is an integer point. In practice, branch and bound methods are typically more efficient than cutting-plane methods, but cutting-plane methods was the first method proven that a MILP solution could be found in a finite number of steps. | ||

__TOC__ | __TOC__ | ||

− | = | + | |

− | ==Gomory's Cuts= | + | |

+ | |||

+ | =Types of Cuts= | ||

+ | |||

+ | Many different cutting plane methods have been developed. Some examples and their performances are listed below.<sup> [1] </sup> | ||

+ | |||

+ | [[File:Tahir1.PNG|thumb|center|upright=3| Comparison of Cutting Plane Methods]] | ||

+ | |||

+ | =Gomory's Cuts= | ||

+ | Cutting-plane methods were first developed by Ralph Gomory in the 1950s and Gomory Cuts remain among the basis of cutting-plane methods.<sup> [2] </sup> | ||

+ | |||

+ | The basic definition of a Gomory Cut is as follows. | ||

+ | Given the system | ||

+ | |||

+ | <math>\sum_{j} \bar a_jx_j \le b_i , x_j = \{0, 1 \}</math> | ||

+ | |||

+ | the Gomory Cut is defined as | ||

+ | |||

+ | <math>\sum_{j} \lfloor \bar a_{j} \rfloor x_j \le \lfloor \bar b_i \rfloor </math>. | ||

+ | |||

+ | ==Example Applying a Gomory Cut to the Simplex Method== | ||

+ | The Gomory Cut method of the above MILP problem is a multi-step process using the following steps: | ||

+ | # Relax the MILP problem to it's complementary LP problem by dropping the requirement that x<sub>i</sub> must be integers. | ||

+ | # Solve the linear programming problem to obtain a basic feasible solution. | ||

+ | # If this vertex is not an integer point then apply a cut to find a hyperplane with the vertex on one side and all feasible integer points on the other and add it to the constraints | ||

+ | # Repeat until a feasible integer solution is found | ||

+ | |||

+ | Using the simplex method to solve a linear program produces a set of equations of the form: | ||

+ | |||

+ | <math>x_i+\sum \bar a_{i,j}x_j=\bar b_i</math> | ||

+ | |||

+ | where ''x<sub>i</sub>'' is the basic variable and all the ''x<sub>j</sub>'''s are the nonbasic variables. The equation can be rewritten to show: | ||

+ | |||

+ | <math>x_i+\sum \lfloor \bar a_{i,j} \rfloor x_j - \lfloor \bar b_i \rfloor = \bar b_i - \lfloor \bar b_i \rfloor - \sum ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j.</math> | ||

+ | |||

+ | For any integer point in the feasible region the right side of this equation must be less than 1 and the left side must be an integer, therefore the inequality | ||

+ | |||

+ | :<math>\bar b_i - \lfloor \bar b_i \rfloor - \sum ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j \le 0</math> | ||

+ | |||

+ | must hold for any integer point in the feasible region. Furthermore, all nonbasic variables are equal to 0 for any basic solution and if ''x<sub>i</sub>'' is not an integer for the basic solution ''x'', | ||

+ | |||

+ | :<math>\bar b_i - \lfloor \bar b_i \rfloor - \sum ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j = \bar b_i - \lfloor \bar b_i \rfloor > 0.</math> | ||

+ | |||

+ | So the inequality above excludes the basic feasible solution and thus is a cut with the desired properties. Introducing a new slack variable x<sub>k</sub> for this inequality, a new constraint is added to the linear program, namely | ||

+ | |||

+ | :<math>x_k + \sum (\lfloor \bar a_{i,j} \rfloor - \bar a_{i,j}) x_j = \lfloor \bar b_i \rfloor - \bar b_i,\, x_k \ge 0,\, x_k \mbox{ an integer}.</math> | ||

+ | |||

+ | =Cover Cuts= | ||

+ | |||

+ | A Cover cut is one of the simplest cutting plane methods, but can still be effectively used to reach a convex hull reformation of a MILP. Starting with | ||

+ | <math>\sum_{j \in J} \bar a_jx_j \le b_i , x_j = \{0, 1 \}</math> | ||

+ | |||

+ | A subset of <math>J</math> can be defined as <math>C</math> such that | ||

+ | <math>\sum_{j \in C} \bar a_j > b_i </math> | ||

+ | |||

+ | Then if all <math>x_j</math> that exist in <math>C</math> have a value of <math>1</math>, the original constraint will not be met. Therefore, a cut can be made in the form of a cover inequality. A valid cover inequality would have the form of | ||

+ | |||

+ | <math>\sum_{j \in C} \bar x_j \le |C| - 1 , x_j = \{0, 1 \}</math> | ||

+ | |||

+ | Multiple cover inequalities can be formulated for different subsets <math>C</math> of the overall set <math>J</math>. Solving for these different cover inequalities and separating them will result in the convex hull reformation of the MILP. <sup> [3] </sup> | ||

+ | |||

+ | ==Example of Cover Cut== | ||

+ | |||

+ | <math>5x_1+5x_2+4x_3 <= 8 x_j = \{0, 1 \}</math> | ||

+ | |||

+ | One example of a valid cover inequality that can be generated from the original problem is | ||

+ | |||

+ | <math>\sum_{j \in C} \bar a_j > b_i </math> Where <math>C</math> is a subset of <math>J</math> that contains <math>x_1, x_2</math>. This can be validated by checking the following constraint: <math>5 + 5 > 8</math> | ||

+ | Therefore a cover inequality can be made using <math>C = {x_1,x_2}</math>. | ||

+ | The resulting inequality would be | ||

+ | <math>x_1 +x_2 \le 1</math>. | ||

+ | |||

+ | This method can be repeated for different subsets <math>C</math> in the overall set <math>J</math>. Other possible cuts are <math>x_2 +x_3 \le 1</math> and | ||

+ | <math>x_1 +x_2 +x_3\le 1</math>. | ||

+ | |||

+ | Adding all three cover inequalities result in the convex hull reformulation of the original MILP problem. <sup> [4] </sup> | ||

+ | #<math>x_1 +x_2 \le 1</math> | ||

+ | #<math>x_2 +x_3 \le 1</math> | ||

+ | #<math>x_1 +x_2 +x_3 \le 1</math> | ||

+ | |||

+ | =Mixed Integer Rounding Cuts= | ||

+ | |||

+ | Mixed integer rounding cuts were derived from the same principles as Gomory cuts and are also among the most effective cutting plane methods. <sup> [4] </sup> | ||

+ | |||

+ | Starting with, | ||

+ | <math>\sum_{j \in J} \bar a_jx_j \le b_i , x_j = \{0, 1 \}</math> | ||

+ | |||

+ | To define a mixed integer rounding inequality, we must define <math>f_j = b_j-a_j\lfloor b_j/a_j \rfloor</math> where <math>f</math> is a weighting factor to be used in the formulation of a rounding inequality. | ||

+ | |||

+ | The mixed integer rounding inequality is defined as | ||

+ | |||

+ | <math>\sum_{j \in J} \bar f_jx_j \le f_j\lceil b_j/a_j \rceil</math>. | ||

+ | |||

+ | =Conclusion= | ||

+ | Cuts can be extremely useful techniques to simplify MILPs. Cutting away unfeasible non-integer solutions will ultimately lead to a convex-hull formation of the MILP. Once at a convex hull, all the extreme points of the feasible region will be valid integer solutions and the MILP can be solved by the LP relaxation of the original problem. Using cutting plane techniques is an extremely helpful way to solve complex MILP problems. | ||

+ | |||

+ | =References= | ||

+ | # Dey, Santanu. "Production Planning by Mixed Integer Programming." Springer Series in Operations Research and Financial Engineering (2006): n. pag. Georgia Institute of Technology. Web. 6 June 2015. | ||

+ | # Avriel, M. Nonlinear Programming: Analysis and Methods. Mineola, NY: Dover Publications, 2003. Print. | ||

+ | #You, Fengqi. "MILP." ChE 345. Evanston. Apr. 2015. Lecture. | ||

+ | #You, Fengqi. "MILP." ChE 345. Evanston. Apr. 2015. Lecture. | ||

+ | #Russell, Michael. "Cutting Planes for Mixed Integer Programming." Department of Combinatorics and Optimization (n.d.): n. pag. University of Waterloo, 17 Jan. 2006. Web. 6 June 2015. |

## Latest revision as of 19:35, 6 June 2015

Author: Tahir Kapoor (ChE 345 Spring 2015)

Stewards: Dajun Yue and Fengqi You

# Introduction

Mixed-integer cuts or Cutting-plane methods is an iterative approach used to simplify the solution of a mixed integer linear programming (MILP) problem. Cutting-plane methods work by first relaxing the MILP to a complementary linear programming problem and cutting the feasible region to narrow down the solution search space to only include feasible solutions. Unlike the branch and bound method, which subdivides the feasible region into multiple sub-regions, mixed-integer cuts result in one feasible region which can be solved using standard linear programming methods. Proper application of mixed-integer cuts will result in a convex hull reformulation of a MILP where every extreme point of the feasible region is an integer point. In practice, branch and bound methods are typically more efficient than cutting-plane methods, but cutting-plane methods was the first method proven that a MILP solution could be found in a finite number of steps.

## Contents |

# Types of Cuts

Many different cutting plane methods have been developed. Some examples and their performances are listed below.^{ [1] }

# Gomory's Cuts

Cutting-plane methods were first developed by Ralph Gomory in the 1950s and Gomory Cuts remain among the basis of cutting-plane methods.^{ [2] }

The basic definition of a Gomory Cut is as follows. Given the system

the Gomory Cut is defined as

.

## Example Applying a Gomory Cut to the Simplex Method

The Gomory Cut method of the above MILP problem is a multi-step process using the following steps:

- Relax the MILP problem to it's complementary LP problem by dropping the requirement that x
_{i}must be integers. - Solve the linear programming problem to obtain a basic feasible solution.
- If this vertex is not an integer point then apply a cut to find a hyperplane with the vertex on one side and all feasible integer points on the other and add it to the constraints
- Repeat until a feasible integer solution is found

Using the simplex method to solve a linear program produces a set of equations of the form:

where *x _{i}* is the basic variable and all the

*x*s are the nonbasic variables. The equation can be rewritten to show:

_{j}'

For any integer point in the feasible region the right side of this equation must be less than 1 and the left side must be an integer, therefore the inequality

must hold for any integer point in the feasible region. Furthermore, all nonbasic variables are equal to 0 for any basic solution and if *x _{i}* is not an integer for the basic solution

*x*,

So the inequality above excludes the basic feasible solution and thus is a cut with the desired properties. Introducing a new slack variable x_{k} for this inequality, a new constraint is added to the linear program, namely

# Cover Cuts

A Cover cut is one of the simplest cutting plane methods, but can still be effectively used to reach a convex hull reformation of a MILP. Starting with

A subset of can be defined as such that

Then if all that exist in have a value of , the original constraint will not be met. Therefore, a cut can be made in the form of a cover inequality. A valid cover inequality would have the form of

Multiple cover inequalities can be formulated for different subsets of the overall set . Solving for these different cover inequalities and separating them will result in the convex hull reformation of the MILP. ^{ [3] }

## Example of Cover Cut

One example of a valid cover inequality that can be generated from the original problem is

Where is a subset of that contains . This can be validated by checking the following constraint: Therefore a cover inequality can be made using . The resulting inequality would be .

This method can be repeated for different subsets in the overall set . Other possible cuts are and .

Adding all three cover inequalities result in the convex hull reformulation of the original MILP problem. ^{ [4] }

# Mixed Integer Rounding Cuts

Mixed integer rounding cuts were derived from the same principles as Gomory cuts and are also among the most effective cutting plane methods. ^{ [4] }

Starting with,

To define a mixed integer rounding inequality, we must define where is a weighting factor to be used in the formulation of a rounding inequality.

The mixed integer rounding inequality is defined as

.

# Conclusion

Cuts can be extremely useful techniques to simplify MILPs. Cutting away unfeasible non-integer solutions will ultimately lead to a convex-hull formation of the MILP. Once at a convex hull, all the extreme points of the feasible region will be valid integer solutions and the MILP can be solved by the LP relaxation of the original problem. Using cutting plane techniques is an extremely helpful way to solve complex MILP problems.

# References

- Dey, Santanu. "Production Planning by Mixed Integer Programming." Springer Series in Operations Research and Financial Engineering (2006): n. pag. Georgia Institute of Technology. Web. 6 June 2015.
- Avriel, M. Nonlinear Programming: Analysis and Methods. Mineola, NY: Dover Publications, 2003. Print.
- You, Fengqi. "MILP." ChE 345. Evanston. Apr. 2015. Lecture.
- You, Fengqi. "MILP." ChE 345. Evanston. Apr. 2015. Lecture.
- Russell, Michael. "Cutting Planes for Mixed Integer Programming." Department of Combinatorics and Optimization (n.d.): n. pag. University of Waterloo, 17 Jan. 2006. Web. 6 June 2015.