English

Linear programming (LP) is nowadays probably the most frequently used optimization technique in science and industry. During the last fifteen years the dual simplex method has become a strong contender in solving large scale LP problems. Furthermore, it constitutes an indispensable subroutine within branch-and-cut methods deployed to solve mixed-integer linear programming problems. Despite of its success and relevance for future research only very publications in research literature discuss mathematical or computational techniques proposed for the dual simplex algorithm from the perspective of implementation. The lack of descriptions of important implementation details has led to a great performance gap between open-source research codes and commercial LP-systems. In this thesis we present the mathematical algorithms, computational techniques and implementation details, which are the key factors for our dual simplex code to close this gap. Special attention is given to three main issues: 1. Dual phase I methods. 2. Exploitation of hypersparsity. 3. Implementation of dual pricing and ratio test. In our study of dual phase I methods we show that the task of minimizing the sum of dual infeasibilities can be explicitly modeled as a subproblem and directly be solved by the dual phase II. This subproblem approach is much easier to implement and as powerful as previously proposed algorithmic methods. Furthermore, we propose a new method, which combines Pan’s dual phase I algorithm and the subproblem approach and turns out to be superior to other methods in our computational tests. We also discuss the impact of LP preprocessing on dual feasibility. Our subroutines to solve the required systems of linear equations are based on an LU-factorization of the basis. We give a mathematical description of this technique, which allows to use only one instead of two permutation matrices in the FTran and BTran operations. Based on this framework, we present the first detailed description of how to exploit hypersparsity in the dual simplex algorithm. We describe several techniques to solve numerically difficult LP problems and reduce the number of degenerate iterations. Here, our main contribution is the conceptual integration of Harris’ ratio test, bound flipping and cost shifting techniques and the description of a sophisticated and efficient implementation. Furthermore, we address important issues of the implementation of dual steepest edge pricing and show how to maintain a vector of primal infeasibilities. Finally we show, that our dual simplex code outperforms the best existing opensource and research codes and is competitive to the leading commercial LP-systems on our most difficult test problems.

Deutsch

Die lineare Programmierung (LP) ist heute die vermutlich meist genutzte Optimierungstechnik in Wirtschaft und Wissenschaft. Während der letzten fünfzehn Jahre hat sich die duale Simplexmethode zu einem der wichtigsten Lösungsverfahren für große LP Probleme entwickelt. Sie ist außerdem ein unverzichtbarer Bestandteil von Branchand-Cut-Verfahren, die zur Lösung von gemischt-ganzzahligen Problemen eingesetzt werden. Trotz ihres erfolgreichen Einsatzes und ihrer Bedeutung für die zukünftige Forschung im Bereich der linearen Programmierung gibt es bis heute relativ wenige wissenschaftliche Veröffentlichungen zum dualen Simplexverfahren. Insbesondere wurden mathematische und numerische Verbesserungen des dualen Simplexalgorithmus bisher kaum aus Implementierungssicht diskutiert. Das Fehlen von Veröffentlichungen über wichtige Implementierungsdetails hat zu einem großen Leistungsvorsprung von kommerziellen LP-Systemen im Vergleich zu Open-Source- und Forschungscodes geführt. In dieser Arbeit präsentieren wir die mathematischen Algorithmen, numerischen Techniken und Implementierungsdetails, die die Schlüsselfaktoren bei der Entwicklung unseres dualen Simplexcodes waren, um diesen Vorsprung wettzumachen. Drei Bereiche werden dabei besonders ausführlich behandelt: 1. Die duale Phase I. 2. Die Ausnutzung von Hypersparsity. 3. Die Implementierung des dualen Pricingschrittes und des dualen Quotiententests. In unserer Untersuchung von Verfahren der dualen Phase I zeigen wir, dass die Aufgabe der Minimierung der dualen Unzulässigkeiten explizit als Unterproblem modelliert und direkt mit der dualen Phase II gelöst werden kann. Dieser Unterproblemansatz ist wesentlich einfacher zu implementieren und dabei ebenso leistungsfähig wie der bekannte algorithmische Ansatz. Weiterhin schlagen wir eine neue Methode vor, die das duale Phase I Verfahren von Pan mit dem Unterproblemansatz kombiniert und den anderen Verfahren in unseren numerischen Tests überlegen ist. Außerdem diskutieren wir den Einfluss des LP-Preprocessing auf die duale Zulässigkeit der Startbasis. Unsere Verfahren zur Lösung der benötigten linearen Gleichungssysteme basieren auf einer LU-Faktorisierung der Basismatrix, die in den FTran und BTran Operationen nur eine statt zwei Permutationsmatrizen benötigt. In diesem Rahmen liefern wir die erste ausführliche Beschreibung von Verfahren zur Ausnutzung von Hypersparsity im dualen Simplexalgorithmus. Die Arbeit enthält mehrere Techniken, die der Lösung von numerisch schwierigen LP Problemen und der Reduzierung der Anzahl degenerierter Iterationen dienen. In diesem Bereich besteht der Hauptbeitrag in der konzeptionellen Integration und ausgefeilten Implementierung der dualen Version von Harris’ Quotiententest und Techniken zum Schrankentausch und zur dynamischen Veränderung von Zielfunktionskoeffizienten. Desweiteren sprechen wir wichtige Implementierungsaspekte des dualen Steepest-Edge Pricings an und zeigen, wie die primalen Unzulässigkeiten effizient in einem Vektor verwaltet werden können. Schließlich weisen wir in einer umfangreichen numerischen Studie nach, dass unser dualer Simplexcode den besten existierenden Open-Source- und Forschungscodes überlegen ist und bei der Lösung unserer schwierigsten Testprobleme mit den führenden kommerziellen Codes mithalten kann.