Optimierung stationärer Ausbauplanung und transienter Netzwerksteuerung durch gemischt-ganzzahlige nichtlineare Programmierung

Nowadays, transmission system operators of energy networks (TSO) have to enable secure energy supply even under challenging transport situations and increasing demand. Hence, they seek a stable network control and regularly expand the capacity of their networks. The challenging questions arise of how to obtain safe network operations for fixed network infrastructure and how to extend the network capacity at minimum cost. In this thesis, we formulate these two questions as mathematical optimization problems and present solution approaches that scale to real-world instances of size and complexity encountered in practice. Model formulations of both problems are located in the field of Mixed-Integer Nonlinear Programming (MINLP). However, global state-of-the-art MINLP solvers are not mature enough to solve or even find primal solutions on large-scale real-world instances since the resulting degree of nonconvexity and nonlinearity pose principal difficulties. For this reason, we develop novel model formulations and optimization algorithms that significantly improve the performance of the solver SCIP. The first part of the thesis focuses on the optimization of stationary network expansions by building new pipelines in parallel to existing ones, so-called looping. Based upon a model reduction approach for multiple loops, we introduce new models for the discrete and split-pipe looping paradigm and compare them with existing models in the literature, both theoretically and empirically. It turns out that our novel split-pipe model performs best in several respects: running time, number of instances solved, and cost savings by up to 7000% over the discrete models. To further improve the performance, we analytically calculate the convex envelope of the nonconvex, nonlinear constraint function f(x,y) = y sgn(x) |x|^a, which models the physical effect of the expansion. In this way, we considerably tighten the convex relaxation of the network expansion problem. The resulting implementation significantly reduces the average solving time by up to 58% on difficult instances. The second part of the thesis deals with the optimization of operations in transient large-scale networks. The problem consists of making day-ahead control decisions that enable feasible energy transport. To this end, we propose a specially-tailored solution approach. First, we aggregate network structures, which TSOs typically consider as of minor importance for the decision-making process. Then, we apply model reformulations that exploit the disjunctive nature of certain network structures and strengthen the linear relaxation. Finally, we present a primal heuristic based on time decomposition. The heuristic solves MINLP sub-models to acquire transport decisions for single time steps. We equip the heuristic with a mechanism that enables moving forward and backward on the time scale to compensate for possibly disadvantageous decisions taken at earlier stages. An extensive computational study shows that our approach reliably generates solutions for 96% to 100% of the instances for three different large-scale real-world networks. Parts of the developed methods are already in use by our industrial cooperation partner Open Grid Europe GmbH to facilitate the respective decision-making processes.Heutzutage müssen Betreiber von Energienetzen auch unter schwierigen Transportsituationen und steigender Bedarfsnachfrage die Energieversorgung sicherstellen. Sehr große Herausforderungen bestehen dabei zum einen in der Gewährleistung des zulässigen Energietransports innerhalb einer gegebenen Netz-Infrastruktur und zum anderen in der kostengünstigen Kapazitäts-Erweiterung durch Netzausbauten. In der vorliegenden Arbeit formulieren wir diese beiden Aufgaben als mathematische Optimierungsprobleme und entwickeln Lösungsansätze für praxisrelevante Instanzen von bedeutender Größe und Komplexität. Die resultierenden Modellformulierungen gehören zur Klasse der gemischt-ganzzahligen nichtlinearen Programmierung (MINLP). Allerdings sind globale MINLP Löser meist nicht in der Lage, große praxisbezogene Probleminstanzen zu lösen bzw. Primallösungen zu finden, da modellinhärente Nichtkonvexitäten und Nichtlinearitäten signifikante Schwierigkeiten im Lösungsprozess darstellen. In dieser Arbeit entwickeln wir Modellformulierungen und Optimierungsalgorithmen, die diese Schwierigkeiten adressieren und die Performanz des Lösers SCIP deutlich verbessert. Der erste Teil dieser Arbeit befasst sich mit der Optimierung von stationären Netzerweiterungen, bei denen Rohre parallel zu existierenden Rohren gebaut werden, sogenannte Loops. Basierend auf einem Modellreduktionsansatz für kosteneffiziente mehrfache Loops, führen wir neue Modellformulierungen für das diskrete und split-pipe Paradigma ein und vergleichen sie theoretisch und experimentell mit Modellen aus der Literatur. Es stellt sich heraus, dass unser neues split-pipe Modell die deutlich beste Performanz aufweist und insgesamt zu Kosteneinsparungen von bis zu 7000% gegenüber den diskreten Modellen führt. Um die Performanz weiter zu verbessern, entwickeln wir die stärkere konvexe Relaxierung des stationären Ausbauproblems. Dazu berechnen wir für die konvexe Einhüllende der nichtkonvexen und nichtlinearen Bedingung f(x,y) = y sgn(x) |x|^a, welche die physikalische Wirkung des Ausbaus darstellt, eine algebraische Lösung in geschlossener Form. Die resultierende Implementierung reduziert die durchschnittliche Rechenzeit um bis zu 58% für schwierige Instanzen. Der zweite Teil der Arbeit beschäftigt sich mit der Optimierung des Betriebs von transienten großen Energienetzen. Ziel ist es, Kontrollentscheidungen zu treffen, die einen zulässigen Energietransport ermöglichen. Zu diesem Zweck entwickeln wir einen mehrstufigen Lösungsansatz. Zunächst aggregieren wir Teile des Netzes, die typischerweise für die Entscheidungsfindung von Netzbetreibern als weniger wichtig angesehen werden. Dann wenden wir Modell-Reformulierungen an, die den disjunkten Charakter einiger Netzstrukturen ausnutzen und die lineare Relaxierung des Problems stärken. Schließlich präsentieren wir eine auf Zeit-Dekomposition basierende Primalheuristik. Hier werden durch das Lösen von MINLP Submodellen Transportentscheidungen für die einzelnen Zeitschritte generiert. Dabei statten wir die Heuristik mit einem Mechanismus aus, der es ermöglicht, auf der Zeitskala vor und zurück zu gehen, um unvorteilhafte Entscheidungen, die in früheren Zeitschritten getroffen wurden, zu dekompensieren. Umfangreiche Rechenexperimente zeigen, dass unser Ansatz zuverlässig Primallösungen für insgesamt 96% bis 100% aller Instanzen für drei verschiedene große reale Netzwerke findet. Teile der in dieser Arbeit entwickelten Methoden sind bereits bei unserem industriellen Projektpartner Open Grid Europe GmbH im Einsatz