Optimization Online


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

Amitabh Basu(abasu***at***math.ucdavis.edu)
Robert Hildebrand(rhildebrand***at***math.ucdavis.edu)
Matthias Koeppe(mkoeppe***at***math.ucdavis.edu)

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 [\emph{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 Cornu\'ejols and Margot [\emph{On the facets of mixed integer programs with two integer variables and two constraints}, Math.\ Programming \textbf{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. \end{abstract}

Keywords: Mixed-Integer Programming, Polyhedral Structure, Cutting Plane Algorithms

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

Citation: Department of Mathematics, University of California, Davis, July (2011)

Download: [PDF]

Entry Submitted: 07/25/2011
Entry Accepted: 07/26/2011
Entry Last Modified: 07/25/2011

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