Bibliothek

Beschreibung: Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.

Beschreibung: The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model and uncertainty in the data pose principal difficulties. The first part of the thesis deals with non-convex quadratic programs. Branch&Bound methods for this problem class depend on tight relaxations. We contribute in several ways: First, we establish a new way to handle missing linearization variables in the well-known Reformulation-Linearization-Technique (RLT). This is implemented into the commercial software CPLEX. Second, we study the optimization of a quadratic objective over the standard simplex or a knapsack constraint. These basic structures appear as part of many complex models. Exploiting connections to the maximum clique problem and RLT, we derive new valid inequalities. Using exact and heuristic separation methods, we demonstrate the impact of the new inequalities on the relaxation and the global optimization of these problems. Third, we strengthen the state-of-the-art relaxation for the pooling problem, a well-known non-convex quadratic problem, which is, for example, relevant in the petrochemical industry. We propose a novel relaxation that captures the essential non-convex structure of the problem but is small enough for an in-depth study. We provide a complete inner description in terms of the extreme points as well as an outer description in terms of inequalities defining its convex hull (which is not a polyhedron). We show that the resulting valid convex inequalities significantly strengthen the standard relaxation of the pooling problem. The second part of this thesis focuses on a common challenge in real world applications, namely, the uncertainty entailed in the input data. We study the extension of a gas transport network, e.g., from our project partner Open Grid Europe GmbH. For a single scenario this maps to a challenging non-convex MINLP. As the future transport patterns are highly uncertain, we propose a robust model to best prepare the network operator for an array of scenarios. We develop a custom decomposition approach that makes use of the hierarchical structure of network extensions and the loose coupling between the scenarios. The algorithm used the single-scenario problem as black-box subproblem allowing the generalization of our approach to problems with the same structure. The scenario-expanded version of this problem is out of reach for today's general-purpose MINLP solvers. Yet our approach provides primal and dual bounds for instances with up to 256 scenarios and solves many of them to optimality. Extensive computational studies show the impact of our work.

Beschreibung: Der bemerkenswerte Erfolg der angewandten mathematischen Optimierung in den letzten Dekaden ist mehr auf Einsichten in mathematische Strukturen zurückzuführen, als auf eine Steigerung der Rechenleistung. In diesem Sinne adressieren wir Anwendungen, in denen Nichtkonvexität und Unsicherheit in den Daten die Hauptschwierigkeiten darstellen. Der erste Teil dieser Arbeit beschäftigt sich mit nichtkonvexen quadratischen Optimierungsproblemen. Relaxierungen sind integraler Bestandteil von \BranchAndBound{}-Lösungsmethoden für diese Problemkategorie. Wir leisten folgende Beiträge: Erstens beschreiben wir eine neue Art fehlende Linearisierungsvariablen, in der so genannten Reformulation-Linearization-Technique (RLT), zu behandeln. Diese wird inzwischen in der kommerziellen Software CPLEX verwendet. Zweitens beschäftigen wir uns mit der Optimierung einer quadratischen Zielfunktion über die Standardsimplex oder einen so genannten Knapsack-Constraint. Solche grundlegenden Strukturen sind Teil vieler komplexer Modelle. Wir benutzen bekannte Verbindungen zum maximalen Cliquenproblem sowie zu RLT, um neue gültige Ungleichungen herzuleiten, die die Relaxierung verstärken. Drittens beschäftigen wir uns mit dem Pooling Problem, das z.B. in der Erdölindustrie relevant ist. Wie leiten eine neue Relaxierung her, die die wesentliche nicht-konvexe Struktur des Problems erfasst, aber klein genug für eine grundlegende Untersuchung ist. Wir geben eine innere Beschreibung in Form der Extrempunkte, sowie eine äußere Beschreibung in Form von Ungleichungen, die die konvexe Hülle (welche im Allgemeinen kein Polyeder ist) beschreiben, an. Wir zeigen, dass neuen die Ungleichungen die Relaxierung des Pooling Problems erheblich verstärken. Der zweite Teil der Arbeit befasst sich mit einer weiteren Herausforderung in realen Anwendungen, nämlich Unsicherheit in den Eingabedaten. Konkret untersuchen wir die Optimierung des Ausbaus eines Gastransportnetzes, wie z.B. von unserem Projektpartner Open Grid Europe GmbH. Dieses Problem ist bereits bei gegebenen Eingabedaten ein schweres nicht-konvexes gemischt-ganzzahliges Optimierungsproblem. Da zukünftige Nutzungsmuster des Netzes mit großer Unsicherheit behaftet sind, beschreiben wir ein robustes Modell, um den Netzbetreiber gegen verschiedene Szenarien abzusichern. Wir entwickeln einen speziellen Dekompositionsalgorithmus unter Berücksichtigung der hierarchischen Struktur der Ausbauten und der schwachen Kopplung zwischen den Szenarien. Unser Ansatz liefert primale und duale Schranken für Instanzen mit bis zu 256 Szenarien und löst viele beweisbar optimal. Umfangreiche Rechnungen bestätigen die Effizient der vorgestellten Methoden.