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}
Citation
Department of Mathematics, University of California, Davis, July (2011)