Some 0/1 polytopes need exponential size extended formulations

• 成果类型: Article
• 署名作者: Rothvoss, Thomas
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0574-3
• 发表日期: 2013
• 页码: 255-268
• 关键词: combinatorial optimization; hierarchy; circuits; graphs

摘要

We prove that there are 0/1 polytopes P subset of R-n that do not admit a compact LP formulation. More precisely we show that for every n there is a set X subset of {0, 1}(n) such that conv(X) must have extension complexity at least 2(n/2.(1-o(1))). In otherwords, 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 subset of P-/poly, our result rules out the existence of a compact formulation for any NP-hard optimization problem even if the formulation may contain arbitrary real numbers.