Optimization Online


On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

Yogesh Awate(yogesh.awate***at***andrew.cmu.edu)
Gerard Cornuejols(gc0v***at***andrew.cmu.edu)
Bertrand Guenin(bguenin***at***math.uwaterloo.ca)
Levent Tuncel(ltuncel***at***math.uwaterloo.ca)

Abstract: We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type~2 triangle (resp. Type~3 triangle; quadrilateral) inequalities, are all within a factor of $1.5$ of the integer hull, and provide examples showing that the approximation factor is not less than $1.125$. There is no fixed approximation ratio for split or Type~1 triangle inequalities however.

Keywords: mixed integer programming, intersection cuts, lattice-free convex sets

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Ontario N2L 3G1, Canada, March 2013.

Download: [PDF]

Entry Submitted: 03/05/2013
Entry Accepted: 03/06/2013
Entry Last Modified: 03/05/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society