Hidden vertices in extensions of polytopes

作者：Pashkovich Kanstantsin; Weltge Stefan^*

来源：Operations Research Letters, 2015, 43(2): 161-164.

DOI：10.1016/j.orl.2015.01.004

• Extended formulation
• Polytope
• Minimal extension
• Projection
• Additional vertex

Some widely known compact extended formulations have the property that each vertex of the corresponding extension polytope is projected onto a vertex of the target polytope. In this paper, we prove that for heptagons with vertices in general position none of the minimum size extensions has this property. Additionally, for any d >= 2 we construct a family of d-polytopes such that at least 1/9 of all vertices of any of their minimum size extensions is not projected onto vertices.

• 出版日期2015-3