paper

Some 0/1 polytopes need exponential size extended formulations

arXiv:1105.0036

Abstract

We prove that there are 0/1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a sets X \subseteq {0,1}^n such that conv(X) must have extension complexity at least 2^{n/2 * (1-o(1))}. In other words, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. Conditioning on NP not contained in P_{/poly}, our result rules out the existence of any compact formulation for the TSP polytope, even if the formulation may contain arbitrary real numbers.

References in corpus (1)

Cited by in corpus (10)