Extended Formulations for Radial Cones

Abstract

This paper studies extended formulations for radial cones at vertices of polyhedra, where the radial cone of a polyhedron $P$ at a vertex $v\in 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$.

10 pages