×

Branched polyhedral systems. (English) Zbl 1285.90082

Eisenbrand, Friedrich (ed.) et al., Integer programming and combinatorial optimization. 14th international conference, IPCO 2010, Lausanne, Switzerland, June 9–11, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13035-9/pbk). Lecture Notes in Computer Science 6080, 177-190 (2010).
Summary: We introduce the framework of branched polyhedral systems that can be used in order to construct extended formulations for polyhedra by combining extended formulations for other polyhedra. The framework, for instance, simultaneously generalizes extended formulations like the well-known ones [E. Balas, SIAM J. Algebraic Discrete Methods 6, 466–486 (1985; Zbl 0592.90070)] for the convex hulls of unions of polyhedra (disjunctive programming) and like those obtained from dynamic programming algorithms for combinatorial optimization problems [R. K. Martin et al., Oper. Res. 38, No. 1, 127–138 (1990; Zbl 0711.90066)]. Using the framework, we construct extended formulations for full orbitopes (the convex hulls of all 0/1-matrices with lexicographically sorted columns), we show for two special matching problems, how branched polyhedral systems can be exploited in order to construct formulations for certain nested combinatorial problems, and we indicate how one can build extended formulations for stable set polytopes using the framework of branched polyhedral systems.
For the entire collection see [Zbl 1189.90006].

MSC:

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