  


Algorithimic and Complexity Results for Cutting Planes Derived from Maximal LatticeFree Convex Sets
Amitabh Basu(abasumath.ucdavis.edu) Abstract: We study a mixed integer linear program with $m$ integer variables and $k$ nonnegative 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.~115]. We describe the facets of this mixed integer linear program via the extreme points of a welldefined 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), 429456]. 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: MixedInteger 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 Modify/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  