Short paths for the simplex algorithm

Abstract

The simplex algorithm is one of the most popular and widely used algorithms for solving linear programming problems. Although being very efficient in practice, no version of the simplex was ever proven to be a polynomial time algorithm from the theoretical prospective, in contrast to its main competitor, the interior point method. The two rivals differ in ideology; while the interior point method, as the name suggests, runs through the interior of the polyhedron of feasible solutions, the simplex proceeds along the edges of it. There has been a lot of prior work showing that every popular simplex version runs into instances where the path that it follows on the feasible polyhedron contains an exponential number of edges. Ever worse than that, despite decades of research, is is still not known whether the diameter of every polytope can be bounded by a polynomial in its dimension and the number of facets (an assumption known as the polynomial Hirsch conjecture), which is a necessary condition for the existence of a polynomial time simplex method. In Chapter 2 of this work, we describe a construction that offers a workaround for the latter issue. We present an extended formulation that establishes a certain relaxed version of the Hirsch conjecture. We improve our construction for low-dimensional polytopes, modify it to account for monotonicity, and ensure that all described extensions can be computed in strongly polynomial time. Moreover, we reduce the general linear programming problem to optimization over the presented extensions. With that we prove that if there is a pivot rule for the simplex algorithmfor which one can bound the number of steps by a polynomial in the diameter of the polyhedron of feasible solutions, then the general linear programming problem can be solved in strongly polynomial time. In addition to the issue of exponentially long paths mentioned above, the simplex algorithm is obstructed by degeneracy. In fact, it can “get stuck” at a degenerate vertex of the feasible polyhedron for exponentiallymany consecutive iterations. While there have beenmany prior works showing how to avoid this phenomenon for a number of special classes of linear programs, no unified approach has ever been suggested. In Chapter 3 we prove that it is always possible to limit the number of consecutive degenerate pivots that the simplex algorithm performs to n −m−1, where n is the number of variables and m is the number of equality constraints of a given linear program in standard equality form. We also obtain a bound on the total number of simplex pivots and show that it is, in fact, strongly polynomial for certain classes of combinatorial LPs.

Der Simplex-Algorithmus ist einer der bekanntesten und am häufigsten verwendeten Algorithmen zur Lösung von linearen Optimierungsproblemen. Obwohl er in der Praxis sehr effizient ist, wurde keine Version des Simplex-Algorithmus jemals theoretisch als ein Polynomialzeitalgorithmus nachgewiesen, im Gegensatz zu seinem Hauptkonkurrenten, der Interior-Point-Methode. Die beiden Rivalen unterscheiden sich in ihrer Ideologie: Während die Interior-Point-Methode, wie der Name schon verrät, durch das Innere des Polyeders der zulässigen Lösungen läuft, bewegt sich der Simplex-Algorithmus entlang der Kanten dieses Polyeders. Es gibt viele vorangegangene Arbeiten, die zeigen, dass jede bekannte Version des Simplex-Algorithmus auf Instanzen stößt, bei denen der von ihm gefolgte Pfad im zulässigen Polyeder eine exponentielle Anzahl von Kanten enthält. Noch problematischer ist, dass trotz Jahrzehnten der Forschung immer noch nicht bekannt ist, ob der Durchmesser jedes Polytops durch ein Polynom in seiner Dimension und der Anzahl der Facetten begrenzt werden kann (eine Annahme, die als polynomiale Hirsch-Vermutung bekannt ist), was eine notwendige Bedingung für die Existenz einer Polynomialzeitversion des Simplex-Verfahrens darstellt. In Kapitel 2 dieser Arbeit beschreiben wir eine Konstruktion, die eine Umgehungslösung für dieses Problem bietet. Wir präsentieren eine erweiterte Formulierung, die eine bestimmte entspannte Version der Hirsch-Vermutung etabliert. Wir verbessern unsere Konstruktion für nieder-dimensionale Polytope, passen sie an, um Monotonie zu berücksichtigen, und stellen sicher, dass alle beschriebenen Erweiterungen in stark polynomialer Zeit berechnet werden können. Darüber hinaus reduzieren wir das allgemeine lineare Optimierungsproblem auf Optimierung über den vorgestellten Erweiterungen. Damit beweisen wir, dass, wenn es eine Pivotregel für den Simplex-Algorithmus gibt, bei der man die Anzahl der Schritte durch ein Polynom im Durchmesser des Polyeders der zulässigen Lösungen begrenzen kann, das allgemeine lineare Optimierungsproblem in stark polynomialer Zeit gelöst werden kann. Zusätzlich zu dem oben erwähnten Problem der exponentiell langen Pfade wird der Simplex-Algorithmus durch Degeneration behindert. In der Tat kann er an einer degenerierten Ecke des zulässigen Polyeders für exponentiell viele aufeinanderfolgenden Iterationen „festhängen“. Während es viele vorangegangene Arbeiten gibt, die zeigen, wie dieses Phänomen für verschiedene spezielle Klassen von linearen Optimierungsproblemen vermieden werden kann, wurde noch kein einheitlicher Ansatz vorgeschlagen. In Kapitel 3 beweisen wir, dass es immer möglich ist, die Anzahl der aufeinanderfolgenden degenerierten Pivots, die der Simplex-Algorithmus ausführt, auf n −m−1 zu begrenzen, wobei n die Anzahl der Variablen und m die Anzahl der Gleichungen eines gegebenen linearen Programms im Gleichungsformat ist. Wir erhalten auch eine Schranke für die Gesamtanzahl der Simplex-Pivots und zeigen, dass diese in der Tat stark polynomial für bestimmte Klassen von kombinatorischen LPs ist.