Hirsch Conjecture and 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.