Mixed-integer cuts

From optimization
Revision as of 16:17, 24 May 2015 by Tahirkapoor (Talk | contribs)

Jump to: navigation, search

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.

Contents


Background

Gomory's Cuts