zbMATH — the first resource for mathematics

Constructing extended formulations from reflection relations. (English) Zbl 1317.90190
Jünger, Michael (ed.) et al., Facets of combinatorial optimization. Festschrift for Martin Grötschel on the occasion of his 65th birthday. Berlin: Springer (ISBN 978-3-642-38188-1/hbk; 978-3-642-38189-8/ebook). 77-100 (2013).
Summary: There are many examples of optimization problems whose associated polyhedra can be described much nicer, and with way less inequalities, by projections of higher dimensional polyhedra than this would be possible in the original space. However, currently not many general tools to construct such extended formulations are available. In this paper, we develop the framework of \(polyhedral relations\) that generalizes inductive constructions of extended formulations via projections, and we particularly elaborate on the special case of reflection relations. The latter ones provide polynomial size extended formulations for several polytopes that can be constructed by iteratedly forming convex hulls of polytopes and (slightly modified) reflections of them at hyperplanes. We demonstrate the use of the framework by deriving small extended formulations for the \(G\)-permutahedra of all finite reflection groups \(G\) (generalizing both M. Goemans’ [“Smallest compact formulation for the permutahedron” http://www-math.mit.edu/~goemans/publ.html] extended formulation of the permutahedron of size \(O(n\log n)\) and A. Ben-Tal and A. Nemirovski’s [Math. Oper. Res. 26, No. 2, 193–205 (2001; Zbl 1082.90133)] extended formulation with \(O(k)\) inequalities for the regular \(2^{k}\)-gon) and for Huffman-polytopes (the convex hulls of the weight-vectors of Huffman codes). This work is an extension of an extended abstract presented at IPCO XV (2011).
For the entire collection see [Zbl 1282.90010].

90C05 Linear programming
Full Text: DOI arXiv