Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets
Skip to main content
eScholarship
Open Access Publications from the University of California

Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets

  • Author(s): Basu, Amitabh
  • Hildebrand, Robert
  • Köppe, Matthias
  • et al.

Published Web Location

https://arxiv.org/pdf/1107.5068.pdf
No data is associated with this publication.
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.

Item not freely available? Link broken?
Report a problem accessing this item