Limits of Linear Programming

该奖项的研究目的是极大地提高我们对线性规划基本极限的理解。这包括对扩展公式大小的已知下界技术的改进，对特定问题的研究，可选的下界技术以及用LP逼近组合和非线性问题的极限的调查。扩展公式是(混合整数)线性规划中用于获得线性优化问题可行域的小描述的重要工具。在许多情况下，扩展配方的使用可以导致在不平等数量方面的指数节省。在通信复杂性方法具有高度相关性的下界技术的背景下，将探索更依赖于多面体的实际性质的替代方法。对于近似扩展公式，将需要对已知方法进行推广，以在组合精确度和几何近似之间进行权衡。主要的研究对象将是匹配多面体和最大割多面体(及其变体)，这两者在复杂性方面都起着至关重要的作用。如果成功，从这个项目中获得的洞察力将大大提高对线性规划最终极限的理解。它还将提供一套新的工具来分析和降低多面体族的扩展复杂性，而不是仅仅依赖组合不变量。这项工作的主要目标是确定线性规划不能提供足够精细的公式的条件。识别这些条件将有助于设计和构建新的优化范例，这种范例可能能够保持线性规划的关键性质(使它们如此成功)，同时仍然超越固有的限制。

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.