Mathematics – Optimization and Control
Scientific paper
2011-07-25
Mathematics
Optimization and Control
35 pages, 15 figures
Scientific paper
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.
Basu Amitabh
Hildebrand Robert
Köppe Matthias
No associations
LandOfFree
Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-92674