Limits of Linear Programming

线性规划的局限性

• 批准号: 1300144
• 负责人: Sebastian Pokutta
• 金额: $ 20万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-04-15 至 2016-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1300144&HistoricalAwards=false
• 关键词: Limits; Linear; Programming

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.

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