- Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations Robert Hildebrand(robdhildebrandgmail.com) Robert Weismantel(robert.weismantelifor.math.ethz.ch) Rico Zenklusen(ricozmath.ethz.ch) Abstract: 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 $\Omega(\sqrt{\sfrac{n}{\log n}})$ 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 non-trivial lower bound on the number of integer variables needed in such settings. Keywords: Extended Formulations, Mixed Integer Programming Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Combinatorial Optimization Citation: Download: [PDF]Entry Submitted: 11/02/2016Entry Accepted: 11/02/2016Entry Last Modified: 11/02/2016Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.