×

Constructing extended formulations from reflection relations. (English) Zbl 1341.90148

Günlük, Oktay (ed.) et al., Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15–17, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20806-5/pbk). Lecture Notes in Computer Science 6655, 287-300 (2011).
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 a 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 as convex hulls of the unions of (exponentially) many copies of an input polytope obtained via sequences of reflections 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. X. Goeman’s [Math. Program. 153, No. 1 (B), 5–11 (2015; Zbl 1322.90048)] 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).
For the entire collection see [Zbl 1216.90002].

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M., Komlós, J., Szemerédi, E.: Sorting in c log n parallel steps. Combinatorica 3(1), 1–19 (1983) · Zbl 0523.68048
[2] Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2), 193–205 (2001) · Zbl 1082.90133
[3] Carr, R.D., Konjevod, G.: Polyhedral combinatorics. In: Greenberg, H. (ed.) Tutorials on emerging methodologies and applications in Operations Research, ch. 2, Springer, Heidelberg (2004)
[4] Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8(1), 1–48 (2010) · Zbl 1219.90193
[5] Fomin, S., Reading, N.: Root systems and generalized associahedra. In: Geometric combinatorics. IAS/Park City Math. Ser., vol. 13, pp. 63–131. AMS, Providence (2007) · Zbl 1147.52005
[6] Goemans, M.: Smallest compact formulation for the permutahedron, http://www-math.mit.edu/stringgoemans/publ.html · Zbl 1322.90048
[7] Humphreys, J.E.: Reflection groups and Coxeter groups. Cambridge Studies in Advanced Mathematics, vol. 29. Cambridge University Press, Cambridge (1990) · Zbl 0725.20028
[8] Kaibel, V., Loos, A.: Branched polyhedral systems. In: Eisenbrand, F., Shepherd, F. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 177–190. Springer, Heidelberg (2010) · Zbl 1285.90082
[9] Kaibel, V., Pashkovich, K., Theis, D.O.: Symmetry matters for the sizes of extended formulations. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 135–148. Springer, Heidelberg (2010) · Zbl 1285.90052
[10] Kipp Martin, R., Rardin, R.L., Campbell, B.A.: Polyhedral characterization of discrete dynamic programming. Oper. Res. 38(1), 127–138 (1990) · Zbl 0711.90066
[11] Nguyen, V.H., Nguyen, T.H., Maurras, J.-F.: On the convex hull of Huffman trees. Electronic Notes in Discrete Mathematics 36, 1009–1016 (2010) · Zbl 1274.90322
[12] Queyranne, M.: Structure of a simple scheduling polyhedron. Math. Programming 58(2, Ser. A), 263–285 (1993) · Zbl 0778.90031
[13] Wolsey, L.A.: Personal communication
[14] Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci. 43(3), 441–466 (1991) · Zbl 0748.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.