Extended Formulations for Radial Cones

This paper studies extended formulations for radial cones at vertices of polyhedra, where the radial cone of a polyhedron P at a vertex v of P is the polyhedron defined by the constraints of P that are active at v. Given an extended formulation for P, it is easy to obtain an extended formulation of comparable size for each its radial cones. On the contrary, it is possible that radial cones of P admit much smaller extended formulations than P itself. A prominent example of this type is the perfect-matching polytope, which cannot be described by subexponential-size extended formulations (Rothvoß 2014). However, Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. Moreover, they generalized their construction to V-join polyhedra. In the same paper, the authors asked whether the same holds for the odd-cut polyhedron, the blocker of the V-join polyhedron. We answer this question negatively. Precisely, we show that radial cones of odd-cut polyhedra cannot be described by subexponential-size extended formulations. To obtain our result, for a polyhedron P of blocking type, we establish a general relationship between its radial cones and certain faces of the blocker of P.

Article

Download

View PDF