English

Mixed-integer programming is a branch of mathematical programming concerned with optimization problems in which a linear objective function is maximized (or minimized) subject to linear constraints and integrality requirements on some of the variables.

Cutting plane methods play a crucial role in accelerating the solution process of mixed-integer programs (MIPs) and are responsible for significant improvements in the performance of MIP solvers. Cutting planes are typically used to strengthen the linear programming relaxation of MIPs by removing fractional solutions, thus reducing the search space of the branch-and-bound algorithm. In this thesis we investigate the generation of general-purpose cutting planes from single- and multiple-constraint relaxations of mixed-integer programs, with an emphasis on computational aspects.

We present a novel algorithm for improving the performance of the Gomory mixed-integer (GMI) cuts. This algorithm is based on the observation that the distance cut off by a GMI cut is affected by the size of the coefficients of the continuous variables in the corresponding row of the simplex tableau. To increase the distance cut off, we propose a reduction algorithm which performs a sequence of pivots on the simplex tableau. We describe in detail our implementation of cut separators for this family of cutting planes as well as for several other families of split cuts from the literature and also highlight important technical details. Moreover, we conduct extensive computational experiments with the discussed cut separators. We show that, in comparison with the GMI cut separator, these cut separators are very effective in reducing the number of branching nodes computed and in increasing the amount of integrality gap closed on a large part of our test set.

We present cut separators which derive cutting planes from multiple rows of a simplex tableau and describe in detail our implementation. We discuss in particular the strengthening of these cuts using the integrality requirements on the non-basic variables. We also perform a detailed computational study of the multi-row cut separators on a large-scale test set. We show that, compared with the split cut separators, multi-row cuts and strengthened multi-row cuts successfully reduce the number of branching nodes on our test set. The multi-row cut separators are, on the other hand, often not competitive with the split cut separators as far as solution times are concerned.

We study techniques for cutting plane selection and management. We present a cut selection algorithm and discuss important technical details. We also discuss various cut quality measures and carry out computational experiments with them. The results of these experiments show that our cut selection algorithm has a positive effect on the performance of an MIP solver.

Deutsch

Die gemischt-ganzzahlige Optimierung ist eine Disziplin der mathematischen Optimierung, die sich mit Optimierungsproblemen beschäftigt, in denen eine lineare Zielfunktion unter Einhaltung von linearen Nebenbedingungen und Ganzzahligkeitsbedingungen auf einigen Variablen maximiert bzw. minimiert wird.

Schnittebenenverfahren spielen bei der Lösung gemischt-ganzzahliger Optimierungsprobleme eine entscheidende Rolle und sind für wesentliche Verbesserungen in der Leistungsfähigkeit von Software zu deren Lösung verantwortlich. Schnittebenen (oder Schnitte) werden typischerweise eingesetzt, um die Schärfe der LP Relaxation durch Ausschluss fraktioneller Lösungen, die nicht zulässig für das gemischt-ganzzahlige Optimierungsproblem sind, zu erhöhen. Dadurch wird der durch den Branch-and-Bound Algorithmus zu untersuchende Lösungsraum eingeschränkt. In dieser Arbeit untersuchen wir die Generierung von allgemeinen Schnittebenen, die aus einer oder durch simultane Betrachtung mehrerer Restriktionen abgeleitet werden können.

Wir präsentieren ein neues Verfahren zur Verbesserung der Leistungsfähigkeit der gemischt-ganzzahligen Gomory-Schnitte. Dieses Verfahren beruht auf der Beobachtung, dass die Distanz zwischen einer fraktionellen LP Lösung und ihrer orthogonalen Projektion auf einer Gomory-Schnittebene von der Größe der Koeffizienten der kontinuierlichen Variablen in der dazugehörigen Zeile des Simplex-Tableaus abhängig ist. Wir schlagen einen Algorithmus vor, dessen Ziel es ist diese Distanz durch Ausführung von Pivotschritten zu vergrößern. Wir beschreiben unsere Implementierung dieses Verfahrens und anderer existierender Ansätze aus der Literatur detailliert und führen umfangreiche numerische Studien durch. Unsere Ergebnisse zeigen, dass unser Ansatz auf einem Großteil der von uns untersuchten Instanzen erfolgreich die Anzahl der im Branch-and-Bound Algorithmus berechneten Knoten reduziert und die duale Schranke verbessert.

Wir präsentieren Separationsalgorithmen, die Schnittebenen durch simultane Betrachtung mehrerer Zeilen eines Simplex-Tableaus ableiten, und beschreiben unsere Implementierung dieser Algorithmen eingehend. Wir diskutieren insbesondere die Verstärkung solcher Schnitte durch Ausnutzung der Ganzzahligkeitsbedingungen auf Nichtbasisvariablen. Die von uns durchgeführten umfangreichen numerischen Studien zeigen, dass die Anwendung von aus mehreren Restriktionen abgeleiteten Schnitten in Reduktionen der vom Branch-and-Bound Algorithmus berechneten Knotenanzahl resultiert. Unsere Studien zeigen jedoch auch, dass die Anwendung dieser Schnitte oftmals zu einer Erhöhung der Lösungszeit führt.

Wir untersuchen Techniken für die Auswahl und die Verwaltung von Schnittebenen. Wir präsentieren einen Algorithmus zur Auswahl von Schnittebenen und diskutieren wichtige technische Details. Wir stellen außerdem verschiedene Qualitätsmaße für Schnittebenen vor und vergleichen diese anhand von numerischen Studien. Diese Studien zeigen, dass unser Auswahlalgorithmus die Leistungsfähigkeit von Software zur Lösung gemischt-ganzzahliger Optimierungsprobleme erhöht.