English

This thesis deals with the implementation and evaluation of one class of separation algorithms for mixed integer programming (MIP) solver software. This class comprises those separation algorithms which use relaxations of mixed integer constraints as their input. These typically are the flow cover cut, flow path cut, and cMIR cut separation algorithms. This thesis discusses the implementation of these three separation algorithms in detail and points out important implementation details. Furthermore, it describes algorithmic improvements for the aggregation and bound substitution steps of the cMIR cut separation algorithm. Concerning the flow path cut separation algorithm, it defines a new family of valid inequalities, called the path mixing inequalities, and shows their relation to the flow path inequalities. It also introduces two new separation algorithms to explicitly generate path mixing cuts and shows how path mixing cuts can be generated using a cMIR cut separation algorithm implemented in a certain way. Finally, a number of implementation details are evaluated in a computational study. This computational study also includes comparisons between the described implementations and introduces a new type of diagram to compare the results of computational experiments with separation algorithms.

Deutsch

Diese Doktorarbeit behandelt die Implementierung und Evaluation einer bestimmten Klasse von Separationsalgorithmen für Software zur Lösung von gemischt-ganzzahligen Optimierungsproblemen. Diese Klasse umfasst solche Separationsalgorithmen, die als Eingabe gemischt-ganzzahlige Restriktionen verwenden. Die typischen Vertreter dieser Klasse sind der Flow Cover Cut, der Flow Path Cut und der cMIR Cut Separationsalgorithmus. In dieser Arbeit wird die Implementierung dieser drei Algorithmen eingehend beschrieben und wichtige implementierungsbezogene Details werden erläutert. Außerdem werden algorithmische Verbesserungen für die Aggregation und Bound Substitution des cMIR Cut Separationsalgorithmus’ vorgestellt. In Bezug auf den Flow Path Cut Separationsalgorithmus wird eine neue Klasse von validen Ungleichungen eingeführt, die so genannten Path Mixing Inequalities, und die Beziehung zu den Flow Path Inequalities herausgearbeitet. Zudem werden zwei neue Separationsalgorithmen eingeführt um Path Mixing Cuts explizit zu generieren und gezeigt, dass Path Mixing Cuts auch implizit durch einen cMIR Cut Separationsalgorithmus erzeugt werden können, wenn dieser auf eine bestimmte Art und Weise implementiert ist. Letztendlich werden eine Reihe von Implementierungsdetails in einer Testreihe untersucht. Diese Testreihe umfasst auch Vergleiche zwischen den verschiedenen beschriebenen Implementierungen und verwendet ein neu entwickelte Diagrammtyp zum Vergleichen von Testreihen mit Separationsalgorithmen.