Optimization Online


Extended Formulations for Radial Cones

Matthias Walter(walter***at***or.rwth-aachen.de)
Stefan Weltge(weltge***at***tum.de)

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 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.

Keywords: radial cones; extension complexity; matching polytope; odd-cut polyhedron

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 05/25/2018
Entry Accepted: 05/29/2018
Entry Last Modified: 05/25/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society