Optimization Online


Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

Robert Hildebrand(robdhildebrand***at***gmail.com)
Robert Weismantel(robert.weismantel***at***ifor.math.ethz.ch)
Rico Zenklusen(ricoz***at***math.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


Download: [PDF]

Entry Submitted: 11/02/2016
Entry Accepted: 11/02/2016
Entry Last Modified: 11/02/2016

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