Laufzeitsenkende Maßnahmen für ein MIP-Optimierungsmodell zur Betriebsplanung eines Multicommodity Energiesystems

Abstract

In dieser Arbeit werden verschiedene Maßnahmen zur Rechner-Laufzeitsenkung anhand eines praktischen Unit-Commitment-Problems untersucht und dargestellt. Beginnend mit einer Einführung in die Mathematik von gemischt-ganzzahligen linaeren Programmen werden an einem eigens erstellten Modell unterschiedliche Formulierungen für ein Unit-Commitment-Problem getestet, um eine möglichst MIP-effiziente Formulierung zu finden. Hierfür werden empirsche Tests durchgeführt, deren Ergebnisse mathematisch interpretiert werden. Für die Formulierung von Mindestfahr- und Stillstandsdauern konnte in dieser Arbeit eine neue, verbesserte Formulierung gefunden werden. Ebenso wird anhand der Formulierung von Anfahr- und Stillsetzindikatoren nachgewiesen, dass in Verbindung mit einem Branch-and-Cut Algorithmus die Vermeidung von binären Variablen nicht zwingend zu einer Laufzeitsenkung führen muss, sondern sogar bedeutend längere Rechner-Laufzeiten implizieren kann. In weiterer Folge wird das untersuchte Problem vorgestellt und verschiedene Klassen für die Maßnahmen zur Laufzeitsenkung definiert. Diese Klassen umfassen Hardware, MIP-effiziente Formulierung, Problemangepasste Lösungsstrategien, technische Erweiterungen und Modifizierungen sowie Modellvereinfachungen. Die Bewertung dieser Maßnahmen wird nach den Kriterien der Lösungsqualität und der Rechner-Laufzeit vorgenommen, und die Auswirkungen der jeweiligen Maßnahme auf die Rechner-Laufzeit des Modells in mehreren Kapiteln präsentiert. Die individuellen Laufzeitveränderungen werden einerseits in Tabellen aufbereitet und andererseits durch anschauliche Graphiken dem geneigten Leser dargestellt. In einem abschließenden Kapitel findet ein Vergleich der Auswirkungen auf die Rechner-Laufzeit aller gesetzten Maßnahmen statt.<br />

In this thesis different strategies are examined in order to reduce the run-time of a practical unit-commitment problem formulated in MIP. It starts with an introduction to the mathematical background of MIP, and continues with testing different formulations of a unit-commitment-problem on a specially-designed model in order find the formulation with the shortest run-time. This is accomplished by empirical tests which are interpreted mathematically. A new formulation of minimal run-times of units is presented. Furthermore, the practical system is presented and different classes of measures in order to reduce the run-time are defined. These classes include: hardware, MIP-efficent formulation, solver strategies, engineering extensions and modifications, and simplifications of the model. The evaluation of the measures follows the criteria of quality of solutions (Gap) and run-time (CPU).