Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on n vertices, with a polynomial number of constraints, requires many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical formulations of common problems in operations research. In particular, it shows that for many classic vehicle routing problems and problems involving matchings, any compact mixed-integer linear description of such a problem requires a large number of integer variables. This provides a first nontrivial lower bound on the number of integer variables needed in such settings.

Authors

• Robert Hildebrand
• Robert Weismantel
• Rico Zenklusen

Keywords

No keywords are indexed for this paper.