11-17
Branched Polyhedral Systems
Preprint series: 11-17, Preprints
- MSC:
- 90C10 Integer programming
- 52B12 Special polytopes (linear programming, centrally symmetric, etc.)
Abstract: 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.g., Balas 1985) for the convex hulls of unions of polyhedra (disjunctive programming) and like those obtained from dynamic programming algorithms for combinatorial optimization problems (due to Martin, Rardin, and Campbell 1990}). 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.
Keywords: Disjunctive Programming, Dynamic Programming
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.