  


Extension Complexity Lower Bounds for MixedInteger Extended Formulations
Robert Hildebrand(robdhildebrandgmail.com) Abstract: We prove that any mixedinteger 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 mixedinteger 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 mixedinteger 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. 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/2016 Modify/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  