View source for Mixed-integer cuts

Author: Tahir Kapoor (ChE 345 Spring 2015)
=Introduction=
Mixed-integer cuts or Cutting-plane method 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__ 

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

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 a basic variable and the ''x<sub>j</sub>'''s are the nonbasic variables. Rewrite this equation so that the integer parts are on the left side and the fractional parts are on the right side:

<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 is less than 1 and the left side is an integer, therefore the common value must be less than or equal to 0. So 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, nonbasic variables are equal to 0s in 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>

=Example=