- Algorithimic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets Amitabh Basu(abasumath.ucdavis.edu) Robert Hildebrand(rhildebrandmath.ucdavis.edu) Matthias Koeppe(mkoeppemath.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/2011Entry Accepted: 07/26/2011Entry Last Modified: 07/25/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.