Limits of Linear Programming

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

The research objective of this award is to tremendously enhance our understanding of the fundamental limits of linear programs. This includes the improvement of known lower bounding techniques for the size of extended formulations, research of problem specific, alternative lower bounding techniques as well as the investigation of the limits of approximating combinatorial and nonlinear problems by LPs. Extended formulations are an important tool in (mixed-integer) linear programming for obtaining small descriptions for the feasible region of linear optimization problems. In many cases, the use of extended formulations can lead to an exponential saving in terms of the number of inequalities. In the context of lower bounding techniques where communication complexity methods are of high relevance alternative methods that rely more on the actual nature of polytopes will be explored. For approximate extended formulations a generalization of known methods will be required to capture the trade-off between combinatorial exactness and geometric approximation. The main objects of study will be the matching polytope and the max-cut polytope (and variants of those), both of which play a crucial role in terms of complexity. If successful, the insights gained from this project will lead to a significantly improved understanding of the ultimate limits of linear programming. It will also provide a new set of tools to analyze and lower bound the extension complexity of families of polytopes while not solely relying on combinatorial invariants. The primary goal of this work is to identify conditions under which linear programs fail to provide sufficiently fine formulations. Identifying these conditions will help in the design and construction of new optimization paradigm that might be able to keep crucial properties of linear programs (which made them so succesful) while still surpassing the inherent limitations.