Paper Info
Title
Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets
Abstract
We study a mixed integer linear program with m integer variables and k non-negative continuous variables in the form of the relaxation of the corner polyhedron that was introduced by Andersen, Louveaux, Weismantel and Wolsey [Inequalities from two rows of a simplex tableau, Proc. IPCO 2007, LNCS, vol. 4513, Springer, pp. 1--15]. We describe the facets of this mixed integer linear program via the extreme points of a well-defined polyhedron. We then utilize this description to give polynomial time algorithms to derive valid inequalities with optimal l_p norm for arbitrary, but fixed m. For the case of m=2, we give a refinement and a new proof of a characterization of the facets by Cornuejols and Margot [On the facets of mixed integer programs with two integer variables and two constraints, Math. Programming 120 (2009), 429--456]. The key point of our approach is that the conditions are much more explicit and can be tested in a more direct manner, removing the need for a reduction algorithm. These results allow us to show that the relaxed corner polyhedron has only polynomially many facets.
Year
Venue
Keywords
2011
CoRR
discrete mathematics,extreme point,cutting plane,convex set
Field
DocType
Volume
Integer,Discrete mathematics,Combinatorics,Mathematical optimization,Branch and price,Polyhedron,Integer points in convex polyhedra,Simplex,Integer programming,Linear programming,Linear programming relaxation,Mathematics
Journal
abs/1107.5068
Citations 
PageRank 
References 
4
0.40
8
Authors
3
Name
Order
Citations
PageRank
Amitabh Basu133127.36
Robert Hildebrand2697.82
Matthias KöPpe319120.95