Difference between revisions of "Mixed-integer cuts"

From optimization
Jump to: navigation, search
(Introduction)
Line 1: Line 1:
 
=Introduction=
 
=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 such that the extreme points lie on an integer.  
+
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. 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.
 
__TOC__
 
__TOC__
 +
 
=Background=
 
=Background=
 
=Gomory's Cuts=
 
=Gomory's Cuts=

Revision as of 16:00, 24 May 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. 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.

Contents


Background

Gomory's Cuts