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.