Entwicklung von Software zur Lösung von gemischt-ganzzahligen Optimierungsmodellen mit einem Branch and Cut Ansatz

Abstract

Durch das Konzept der strengen LP-Relaxierung eines gemischt-ganzzahligen Optimierungsmodells konnten große Fortschritte in der ganzzahligen Optimierung erzielt werden. In dieser Arbeit werden wichtige Verfahren zur Bestimmung der strengen LP Relaxierung eines gemsicht-ganzzahligen Optimierungsmodellsvorgestellt. Dabei konnten insbesondere durch Überlegungen bezüglich Cover Cuts, Clique Cuts und Gomory Cuts grundsätzliche Verbesserungen erzielt werden. Zu diesen Verbesserungen zählen: der Einsatz von verschiedenen Lifting-Reihenfolgen bei der Generierung von Cover Cuts, sowie das exakte Lösen der während des Liftens auftreten Knapsack Probleme, ein speziell für Clique Cuts erarbeiteter Lifting-Prozess, der zum Ziel hat einen möglichst verletzten Clique Cut zu generieren und sinnvolle Auswahlkriterien bei der Ableitung von Mixed-Integer-Gomory Cuts, die dafür sorgen, dass nur bestimmte und insgesamt nicht zu viele Cuts an das Modell angehangen werden. Des Weiteren wird darauf eingegangen, welche der Verfahren im Rahmen eines Branch-and-Cut Ansatzes eingesetzt werden sollen. Eine der wichtigsten Eigenschaften eines Cuts im Rahmen des Branch-and-Cut-Prozesses ist seine Gültigkeit. Dabei wird in global und lokal gültige Cuts unterschieden. Eine Vielzahl von Cuts ist lediglich lokal gültig und somit nicht überall im Baum einsetzbar. Im Rahmen dieser Arbeit wird neben einem Liften zur globalen Gültigkeit ein Ansatz zur Handhabung von lokal gültigen Cuts entwickelt. Darüber hinaus werden allgemeingültige Überlegungen zum Liften von Variablen angestellt, die zu der Erkenntnis führen, dass theoretisch jede beliebige 0 1-Variable geliftet werden kann. Verschiedene Strategien zur Regulierung des Einsatzes der Verfahren im Rahmen des Branch- and-Cut-Prozesses werden getestet und entsprechend ausgewertet. Im Ergebnis wird eine Strategie vorgestellt, die bei einer Vielzahl von Modellen zu den besten Lösungszeiten führt. Basis für die vorliegende Arbeit bildet die Mathematischen OPtimierungs Software MOPS . MOPS wird seit mehr als 20 Jahren in den verschiedensten praktischen Anwendungen eingesetzt. Durch die Möglichkeit die erarbeiteten Überlegungen in diese Optimierungssoftware zu implementieren, konnten die theoretisch behandelten Fragen auch praktisch getestet werden.

The concept of the strong LP-relaxation of a mixed-integer optimization model is of great importance for solving large and difficult mixed integer optimization problems. This thesis presents some of the important procedures to derive a strong LP-relaxation of a mixed-integer optimization model. Especially by considering cover cuts, clique cuts and mixed integer gomory cuts improvements could be achieved. Among these improvements is the use of different lifting sequences while generating cover cuts, the exact solving of knapsack problems during that lifting process, as well as a specific lifting process for clique cuts and useful selection criteria for the generation of mixed integer gomory guts. These criteria make sure, that only certain and not too many mixed integer gomory cuts are appended to the model. Additionally it is analyzed which of these techniques are useful within a branch-and-cut algorithm. One of the most important attributes of a cut within a branch-and- cut framework is its validity. There are global and local valid cuts. Apart from lifting a cut to global validity an approach is presented, that provides a useful handling of local valid cuts. Furthermore general considerations concerning the lifting of any 0-1-variable lead to a lifting procedure which offers the opportunity to possibly lift any 0-1-variable. Several strategies to when and what techniques should be used within a branch-and-cut framework are tested and analysed. As result a strategy that leads to the best solution times for most of the tested models is presented. The algorithms are implemented in MOPS. MOPS is a mathematical optimization system that is used in various commercial applications for more than 20 years. Given the possibility to implement the theoretical ideas their practical usefulness could be tested.