Maria Albach (Master Kolloquium): Verfeinerte Schnittauswahl für das Benders-Dekompositionsverfahren zur Dimensionierung von Energienetzen mit Speichern

@Algorithmische Algebra und Diskrete Mathematik

 

Abstract.  Wir stellen verschiedene Varianten eines Benders-Dekompositionsverfahrens zur kostenoptimalen Dimensionierung von Energienetzen vor, welche neben Übertragungsleitungen auch Energiespeicher enthalten. Dabei sollen die Kapazitäten der Leitungen und der Speicher so bestimmt werden, dass mehrere gegebene Zeitreihen aus Energienachfrage und -angeboten an den Netzknoten realisierbar sind. Das Problem wird zunächst als ein gemischt-ganzzahliges Programm formuliert, dessen Nebenbedingungsmatrix eine Blockdiagonalstruktur aufweist. Diese Eigenschaft wird genutzt, um das Modell im Rahmen eines Benders-Dekompositionsverfahrens in ein relaxiertes Master-Problem und mehrere Client-Probleme zur Erzeugung von Ungleichungen für das Master-Problem zu zerlegen. Diese sind jeweils leichter zu lösen als das ursprüngliche Modell. Im Rahmen der Masterarbeit wurden unterschiedliche Varianten der Formulierung der ClientProbleme und entsprechende Varianten der Erzeugung von gültigen Ungleichungen für das MasterProblem untersucht und implementiert. Für die daraus resultierenden Varianten des Dekompositionsverfahrens wurden die Qualität der gefunden Ungleichungen und die erzielten Lösungszeiten miteinander verglichen. Außerdem wurden der Einfluss der Anzahl der pro Iteration zu lösenden Client-Problemen und eines Rundungsmechanismus zur Verbesserung der gefundenen Ungleichungen auf die Laufzeit des Verfahrens untersucht. Die Ergebnisse zeigen, dass sich das betrachtete Netzwerkdesignproblem mit Speichern grundsätzlich gut mit Hilfe eines Benders-Dekompositionsverfahrens lösen lässt. Einer der drei verwendeten Ansätze, in welchem lediglich minimal unzulässige Teilsysteme im Client-Problem gesucht werden, führt dabei zu einem deutlich effizienteren Verfahren für die gewählte Benchmark-Instanz als die beiden anderen untersuchten Ansätze.

 

Vor diesem Vortrag, ab 16.45 Uhr, gibt es wieder Kaffee und Tee im Raum 1404.

Verwandte Links