Exakte gemischt-ganzzahlige Optimierung

In this thesis, we develop and implement an efficient algorithm that can exactly solve instances of the mixed-integer programming problem that are given by rational data. For a feasible instance, a truly optimal solution will be computed; for an infeasible instance, a provably correct infeasibility certificate will be issued. Our exact mixed-integer programming solver is part of the constraint integer programming software SCIP, which is developed and maintained at the Zuse Institute Berlin. Mixed-integer programming solvers have experienced tremendous progress in the last decades, while almost no attention has been paid to exact computations. Most mixed-integer programming solvers, in particular, the state-of-the-art ones CPLEX, Gurobi, MOSEK, SCIP, and Xpress, are numerical solvers, i.e., they use finite-precision binary floating-point arithmetic, which is a compromise between speed and correctness. Such solvers cannot provide any guarantee of correct results. Due to a number of reasons, for many industrial applications near optimal solutions are sufficient. This situation changes fundamentally when mixed-integer programming is used to establish theoretical results, when feasibility questions are considered, and when serious legal and financial consequences may result from incorrect solutions. To underline the necessity of exact solvers, this thesis, first, analyzes how strong the error-proneness inherent in finite-precision binary floating-point systems influences the results of numerical mixed-integer programming solvers. We employ two important theoretical concepts from numerical mathematics therefor: condition of a problem instance and stability of an algorithm. In addition, we test the stability of SCIP on the Miplib benchmarking libraries, discuss how to identify instances of the mixed-integer programming problem on which current solvers face numerical difficulties, and build the first large test set of numerically difficult instances. This thesis, then, shows that it is possible to solve instances of the mixed-integer programming problem exactly over the rational numbers without introducing a large overhead in running time compared to solving them numerically. This applies to numerically easy as well as to numerically difficult instances. While earlier attempts in that direction showed slow-downs of orders of magnitudes, we provide the first efficient exact branch-and-bound solver. As our focus is exclusively on the branch-and-bound procedure, we compared the exact solver against a numerical solver restricted to pure branch-and-bound. The key ingredients of the exact solver are as follows. The first one is the new hybrid rational/safe floating-point approach. The second one is to dynamically choose the fastest of several safe dual bounding methods depending on the structure of the instance. The third one is the sophisticated integration of iterative refinement for linear programming, a new technique to improve the stability of numerical linear programming solvers, into the solution process of the exact mixed-integer programming solver.In dieser Arbeit entwickeln und implementieren wir einen effizienten Algorithmus, der Instanzen des gemischt-ganzzahligen Optimierungsproblems, die durch rationale Daten gegeben sind, exakt lösen kann. Für zulässige Instanzen wird eine korrekte Optimallösung berechnet; für unzulässige Instanzen ein beweisbar korrektes Unzulässigkeitszertifikat. Unser exakter gemischt-ganzzahliger Optimierungslöser ist Teil der Constraint Integer Programming Software SCIP, die am Zuse-Institut Berlin entwickelt und gepflegt wird. In den letzten Jahrzehnten haben sich die Löser für das gemischt-ganzzahlige Optimierungsproblem enorm weiterentwickelt. Die Berechnung von exakten Ergebnissen spielte dabei jedoch fast keine Rolle. Die meisten Löser, insbesondere die State of the Art Löser CPLEX, Gurobi, MOSEK, SCIP, and Xpress, sind numerische Löser, d.h. sie verwenden binäre Gleitkommaarithmetik mit endlicher Genauigkeit, welches einen Kompromiss zwischen Geschwindigkeit und Korrektheit darstellt. Solche Löser können keine Garantie dafür geben, dass die berechneten Antworten korrekt sind. Für viele Industrieanwendungen reicht es aus, annähernd optimale Lösungen für zulässige Instanzen berechnen zu können. Die Lage ändert sich jedoch fundamental, wenn gemischt-ganzzahlige Optimierung verwendet wird, um theoretische Fragen zu untersuchen, wenn Instanzen reine Zulässigkeitsprobleme sind, und wenn falsche Antworten schwerwiegende rechtliche und finanzielle Konsequenzen haben können. Um die Notwendigkeit exakter Löser zu unterstreichen, analysiert diese Arbeit zunächst, wie stark die Fehleranfälligkeit, die der Gleitkommaarithmetik innewohnt, die Ergebnisse von numerischen Optimierungslösern beeinflussen kann. Wir verwenden hierfür zwei wichtige theoretische Konzepte aus der numerischen Mathematik: Kondition einer Probleminstanz und Stabilität eines Algorithmus. Zusätzlich testen wir die Stabilität von SCIP auf den Miplib Benchmarking Bibliotheken, diskutieren, wie man Instanzen des gemischt-ganzzahligen Optimierungsproblems identifizieren kann, auf denen gängige Löser numerische Schwierigkeiten aufweisen und bauen die erste große Bibliothek von numerische schwierigen Instanzen. Im Anschluss zeigt diese Arbeit, dass man Instanzen des gemischt-ganzzahligen Optimierungsproblems exakt lösen kann, ohne dabei die Rechenzeit dramatisch zu erhöhen. Dies lässt sich sowohl für numerisch einfache als auch für numerisch schwierige Instanzen erzielen. Während frühere Arbeiten in diese Richtung enorme Einbußen bei der Rechenzeit aufwiesen, liefern wir den ersten effizienten exakten Branch-und-Bound Löser. Da wir uns auf die Ausgestaltung das Branch-und-Bound Verfahrens konzentriert haben, wurde der exakte Löser mit einem numerischen Löser verglichen, der auf reines Branch-und-Bound eingeschränkt wurde. Unser exakter Löser zeichnet sich durch die folgenden Punkte aus. Wir haben einen hybriden Branch-und-Bound Ansatz entwickelt, der rationale Arithmetik mit sicherer Gleitkommaarithmetik verbindet. Wir benutzen verschiedene Methoden zur Berechnung sicherer Dualschranken. An jedem Branch-und-Bound Knoten wird anhand der Struktur der zu lösenden Instanz die potenziell schnellste Methode ausgewählt. Wir haben Iterative Refinement für das lineare Optimierungsproblem entwickelt. Dieses Verfahren verbessert die Stabilität von numerischen Lösern für das lineare Optimierungsproblem. Darüber hinaus kann es die Rechenzeit von exakten Lösern für das gemischt-ganzzahlige Optimierungsproblem deutlich reduzieren; dies erfordert jedoch eine ausgefeilte Integration in dessen Lösungsprozess