Extended Formulations for Combinatorial Polytopes

摘要: i Abstract Typically polytopes arising from real world problems have a lot of facets. In some cases even no linear descriptions for them are known. On the other hand many these can be described much nicer and with less facets using extended formulations, i.e. as projection simpler higher dimensional polytopes. The presented work studies formulations polytopes: possibilities to construct limitations them. first part, known techniques constructions reviewed new framework polyhedral relations (see Kaibel Pashkovich [2011]) is presented. We in particular elaborate on special case reflection relations. Reflection provide several that constructed by iteratively taking convex hulls their refelections at hyperplanes. Using this we able derive small G-permutahedra all finite groups G. second part deals which use structures graphs involved combinatorial problems. Here present apply few changes formulation Gerards perfect matching polytope genus order reduce its size. Furthermore compact proof an Rivin subtour elimination provided. third (partly based joint Volker Kaibel, Samuel Fiorini Dirk Oliver Theis, see Fiorini, Pashkovich, Theis [2011a]) involves general questions primal interest here lower bounds formulations. study different obtain bounds, could derived so called non-negative factorizations slack matrix initial polytope. minimal such factorization provides number inequalities needed formulation. compare techniques, find examples they give tight complexity extensions. fourth impact symmetry sizes showed certain constrained cardinality cycle there exist polynomial symmetric but non-symmetric ones (for further details [2010]). Beyond results thesis also contains showing well permutahedron via Birkhoff best (up constant factor) one among [2009]).Typically [2009]).