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.

Last modified

• 11/29/2018

Creator

• Tahir Kapoor

DOI

• https://doi.org/10.21985/N21B3D

Keyword

• Mixed-integer
• linear programming

Rights statement

• In Copyright