Hirsch Conjecture and Linear Programming

赫希猜想和线性规划

• 批准号: 9800053
• 负责人: Nagabhushana Prabhu
• 金额: $ 9.82万
• 依托单位: Purdue Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-01 至 2002-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9800053&HistoricalAwards=false
• 关键词: Hirsch; Conjecture; Linear; Programming

The focus of this research is the Hirsch Conjecture which claims that the edge-diameter of a (d,n)-polytope -- a d-polytope with n facets -- is at most n-d. The edge-diameter of the polyhedral feasible region of a Linear Program is of interest since it provides a lower bound on the worst-case behavior of any edge- following Linear Programming algorithm. Considerable research effort has been expended in the past on the Hirsch Conjecture and its relatives due to their crucial role in the quest to understand and improve the worst case behavior of the Simplex method. Despite four decades of research however, even a polynomial upper bound on the edge-diameter of a (d,n)-polytope has remained elusive, and the Hirsch Conjecture and its relatives remain among the most important unresolved problems in the theory of Linear Programming. In contrast to earlier attacks on the conjecture, which analyze the combinatorial structure of polytopes, this research attempts to determine whether or not the space of all Hirsch polytopes (polytopes for which Hirsch Conjecture is true) is a proper subspace of the space of all polytopes. The research will study the geometric properties of the space of Hirsch polytopes in an attempt to determine if the complementary subspace of counterexamples is empty.

本文的研究重点是赫希猜想，它声称一个(d，n)-多面体--一个有n个面的d-多面体--的边径至多为n-d。线性规划的多面体可行域的边径是有意义的，因为它为任何边跟随线性规划算法的最坏情况提供了一个下界。由于Hirsch猜想在理解和改进单纯形法的最坏情况下的行为方面所起的关键作用，过去人们对Hirsch猜想及其近亲进行了大量的研究工作。然而，尽管经过了40年的研究，(d，n)-多面体的边径的多项式上界仍然难以捉摸，而Hirsch猜想及其相关问题仍然是线性规划理论中最重要的悬而未决的问题之一。与先前分析多面体组合结构的猜想的攻击不同，本研究试图确定所有Hirsch多面体(Hirsch猜想成立的多面体)的空间是否是所有多面体空间的真子空间。这项研究将研究赫希多面体空间的几何性质，试图确定反例的补子空间是否为空。