The polytopes associated with combinatorial optimization problems can have quite a complicated facet structure, even for problems that can be solved in polynomial time. In many cases, however, one can obtain such polytopes as projections of much simpler polyhedra, whose linear descriptions then are called extended formulations. In the first part of the talk we will discuss some examples and tools for constructing extended formulations, while in the second part the question of fundamental limits of the approach is addressed. In contrast to a conjecture of Yannakakis (1991), we show that the minimal sizes of extended formulations of certain matching and cycle polytopes for complete graphs severely depend on whether one imposes symmetry requirements or not. The talk is based on joint work with Andreas Loos, Kanstantsin Pashkovich, and Dirk O. Theis.
Copyright. All Rights Reserved.