TY - JOUR A1 - Schmidt, Martin A1 - Assmann, Denis A1 - Burlacu, Robert A1 - Humpola, Jesco A1 - Joormann, Imke A1 - Kanelakis, Nikolaos A1 - Koch, Thorsten A1 - Oucherif, Djamal A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schwarz, Robert A1 - Sirvent, Matthias T1 - GasLib – A Library of Gas Network Instances JF - Data Y1 - 2017 U6 - https://doi.org/10.3390/data2040040 VL - 2 IS - 4 ER - TY - JOUR A1 - Pfetsch, Marc A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Geißler, Nina A1 - Gollmer, Ralf A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Vigerske, Stefan A1 - Willert, Bernhard T1 - Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions JF - Optimization Methods and Software N2 - In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before. Y1 - 2014 U6 - https://doi.org/10.1080/10556788.2014.888426 PB - Taylor & Francis ER - TY - CHAP A1 - Martin, Alexander A1 - Geißler, Björn A1 - Heyn, Christine A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Morsi, Antonio A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Optimierung Technischer Kapazitäten in Gasnetzen T2 - Optimierung in der Energiewirtschaft Y1 - 2011 SP - 105 EP - 114 PB - VDI-Verlag, Düsseldorf ER - TY - JOUR A1 - Humpola, Jesco A1 - Serrano, Felipe T1 - Sufficient pruning conditions for MINLP in gas network design JF - EURO Journal on Computational Optimization N2 - One-quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology optimization problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. We offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex continuous nonlinear program (NLP) can be certified by solving an MILP. This result provides an efficient pruning procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speedup for the necessary computations. Y1 - 2017 U6 - https://doi.org/10.1007/s13675-016-0077-8 VL - 5 IS - 1-2 SP - 239 EP - 261 PB - Springer Berlin Heidelberg ER - TY - JOUR A1 - Humpola, Jesco A1 - Lehmann, Thomas A1 - Fügenschuh, Armin T1 - A primal heuristic for optimizing the topology of gas networks based on dual information JF - EURO Journal on Computational Optimization N2 - We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP. Y1 - 2015 U6 - https://doi.org/10.1007/s13675-014-0029-0 VL - 3 IS - 1 SP - 53 EP - 78 ER - TY - JOUR A1 - Humpola, Jesco A1 - Fügenschuh, Armin A1 - Koch, Thorsten T1 - Valid inequalities for the topology optimization problem in gas network design JF - OR Spectrum N2 - One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euro per km extending the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. Unfortunately, current mathematical methods are not capable of solving the arising network design problems due to their size and complexity. In this article, we will show how to apply optimization methods that can converge to a proven global optimal solution. By introducing a new class of valid inequalities that improve the relaxation of our mixed-integer nonlinear programming model, we are able to speed up the necessary computations substantially. Y1 - 2016 U6 - https://doi.org/https://doi.org/10.1007/s00291-015-0390-2 VL - 38 IS - 3 SP - 597 EP - 631 PB - Springer CY - Berlin Heidelberg ER - TY - CHAP A1 - Humpola, Jesco A1 - Fügenschuh, Armin A1 - Hiller, Benjamin A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Lenz, Ralf A1 - Schwarz, Robert A1 - Schweiger, Jonas T1 - The Specialized MINLP Approach T2 - Evaluating Gas Network Capacities N2 - We propose an approach to solve the validation of nominations problem using mixed-integer nonlinear programming (MINLP) methods. Our approach handles both the discrete settings and the nonlinear aspects of gas physics. Our main contribution is an innovative coupling of mixed-integer (linear) programming (MILP) methods with nonlinear programming (NLP) that exploits the special structure of a suitable approximation of gas physics, resulting in a global optimization method for this type of problem. Y1 - 2015 SN - 9781611973686 VL - SIAM-MOS series on Optimization ER - TY - JOUR A1 - Humpola, Jesco A1 - Fügenschuh, Armin T1 - Convex reformulations for solving a nonlinear network design problem JF - Computational Optimization and Applications N2 - We consider a nonlinear nonconvex network design problem that arises, for example, in natural gas or water transmission networks. Given is such a network with active and passive components, that is, valves, compressors, control valves (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes in the network. The active elements are associated with costs when used. Besides flow conservation constraints in the nodes, the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is to compute a cost minimal setting of the active components and numerical values for the flow and node potentials. We examine different (convex) relaxations for a subproblem of the design problem and benefit from them within a branch-and-bound approach. We compare different approaches based on nonlinear optimization numerically on a set of test instances. Y1 - 2015 U6 - https://doi.org/10.1007/s10589-015-9756-2 VL - 62 IS - 3 SP - 717 EP - 759 PB - Springer US ER - TY - THES A1 - Humpola, Jesco T1 - Gas Network Optimization by MINLP N2 - One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. The challenging question is how to expand and operate the network in order to facilitate the transportation of specified gas quantities at minimum cost. This task can be formulated as a mathematical optimization problem that reflects to real-world instances of enormous size and complexity. The aim of this thesis is the development of novel theory and optimization algorithms which make it possible to solve these problems. Gas network topology optimization problems can be modeled as nonlinear mixed-integer programs (MINLPs). Such an MINLP gives rise to a so-called active transmission problem (ATP), a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. The key to solving the ATP as well as the overall gas network topology optimization problem and the main contribution of this thesis is a novel domain relaxation of the variable bounds and constraints in combination with a penalization in the objective function. In case the domain relaxation does not yield a primal feasible solution for the ATP we offer novel sufficient conditions for proving the infeasibility of the ATP. These conditions can be expressed in the form of an MILP, i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. If the gas network consists only of pipes and valves, the ATP turns into a passive transmission problem (PTP). Although its constraints are non-convex, its domain relaxation can be proven to be convex. Consequently, the feasibility of the PTP can be checked directly in an efficient way. Another advantage of the passive case is that the solution of the domain relaxation gives rise to a cutting plane for the overall topology optimization problem that expresses the infeasibility of the PTP. This cut is obtained by a Benders argument from the Lagrange function of the domain relaxation augmented by a specially tailored pc-regularization. These cuts provide tight lower bounds for the passive gas network topology optimization problem. The domain relaxation does not only provide certificates of infeasibility and cutting planes, it can also be used to construct feasible primal solutions. We make use of parametric sensitivity analysis in order to identify binary variables to be switched based on dual information. This approach allows for the first time to compute directly MINLP solutions for large-scale gas network topology optimization problems. All the research in this thesis has been realized within the collaborative research project "Forschungskooperation Netzoptimierung (ForNe)". The developed software is in use by the cooperation partner Open Grid Europe GmbH. Parts of this thesis have been published in book chapters, journal articles and technical reports. An overview of the topics and solution approaches within the research project is given by Martin et al. (2011) and Fügenschuh et al. (2013). Gas network operation approaches and solution methods are described in detail by Pfetsch et al. (2014) and with a special focus on topology optimization in Fügenschuh et al. (2011). The primal heuristic presented in this thesis is published by Humpola et al. (2014b). The method for pruning nodes of the branch-and-bound tree for an approximation of the original problem is described in Fügenschuh and Humpola (2013) and Humpola et al. (2014a). The Benders like inequality is introduced by Humpola and Fügenschuh (2013). N2 - Ein Viertel des europäischen Energiebedarfs wird durch Gas gedeckt, das durch ein europaweites Pipelinesystem verteilt wird. Aufgrund von Ausbaukosten von 1 Mio. Euro pro Kilometer ist der Netzausbau ein Milliardenunterfangen. Die größte Herausforderung besteht darin zu entscheiden, wie das Netzwerk kostengünstig ausgebaut und genutzt werden kann, um notwendige Gasmengen zu transportieren. Diese Aufgabe kann mit Hilfe eines mathematischen Optimierungsproblems formuliert werden, wobei anwendungsnahe Instanzen eine enorme Größe und Komplexität aufweisen. Ziel der vorliegenden Arbeit ist die Entwicklung neuer mathematischer Theorien und damit einhergehender Optimierungsalgorithmen, die es ermöglichen, derartige Probleme zu lösen. Die Optimierung der Topologie eines Gasnetzwerks kann mit Hilfe eines nichtlinearen gemischt-ganzzahligen Programms (MINLP) modelliert werden. Durch Fixierung aller ganzzahligen Variablen ergibt sich ein kontinuierliches Zulässigkeitsproblem, das als aktives Transmissionsproblem (ATP) bezeichnet wird. Die zentrale Methode um dieses ATP zu lösen, ist eine neuartige Relaxierung, welche Variablenschranken und einige Nebenbedingungen relaxiert und in der Zielfunktion bestraft. Diese Relaxierung bildet den Kern der in dieser Arbeit vorgestellten Theorie und ermöglicht so die effiziente Lösung der Topologieoptimierung eines Gasnetzwerkes. Für den Fall, dass die Relaxierung keine Primallösung für das ATP liefert, ist es uns gelungen, hinreichende Bedingungen für die Unzulässigkeit des ATP zu formulieren, die durch ein MILP dargestellt werden. Kurz gefasst kann die Unzulässigkeit eines nicht-konvexen NLP durch Lösung eines MILP bewiesen werden. Beide Methoden liefern effiziente Schranken in einem branch-and-bound Lösungsverfahren. Besteht ein Gasnetzwerk nur aus Rohren und Schiebern, dann wird das ATP als passives Transmissionsproblem (PTP) bezeichnet. Obwohl die Nebenbedingungen des PTP nicht konvex sind, konnten wir zeigen, dass seine Relaxierung konvex ist. Daher kann die Unzulässigkeit des PTP direkt auf effiziente Weise geprüft werden. Außerdem können mit Hilfe der Relaxierung in diesem speziellen Fall Schnittebenen für das Topologieoptimierungsproblem aufgestellt werden. Diese repräsentieren die Unzulässigkeit des PTP und folgen aus der Lagrange Funktion der Relaxierung zusammen mit einer speziellen Erweiterung, der sogenannten pc-Regularisierung. Abgesehen von den genannten Klassifizierungen kann die Relaxierung auch genutzt werden, um primale Lösungen zu konstruieren. Hier nutzen wir die parametrische Sensitivitätsanalyse, um mit Hilfe dualer Informationen Binärvariablen des ATP zu identifizieren, deren Werte angepasst werden müssen. Dieser Ansatz erlaubt es zum ersten Mal, direkt MINLP Lösungen für das Topologieoptimierungsproblem realer Gasnetzwerke zu berechnen. Die Resultate dieser Arbeit wurden im Rahmen des Forschungsprojekts "Forschungskooperation Netzoptimierung (ForNe)" erarbeitet. Die entwickelte Software wird vom Kooperationspartner Open Grid Europe GmbH aktiv genutzt. Teile dieser Arbeit sind in Buchkapiteln, Journalen und technischen Berichten publiziert. Eine Übersicht über die Themen und Lösungsansätze im ForNe-Projekt veröffentlichten Martin u. a. (2011) und Fügenschuh u. a. (2013). Für Lösungsmethoden für die operative Nutzung von Gasnetzwerken verweisen wir auf Pfetsch u. a. (2014). Ansätze für eine Topologieoptimierung wurden von Fügenschuh u. a. (2011) beschrieben. Die in dieser Arbeit präsentierte primale Heuristik ist publiziert von Humpola u. a. (2014b). Die genannte Methode, um Knoten innerhalb des branch-and-bound Baums abzuschneiden, wurde für eine Approximation des Topologieproblems von Fügenschuh und Humpola (2013) und Humpola u. a. (2014a) beschrieben. Ein Bericht über die Ungleichungen nach Benders ist in Humpola und Fügenschuh (2013) nachzulesen. T2 - Gas Netzwerk Optimierung mittels MINLP Y1 - 2014 UR - http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/5904 ER - TY - CHAP A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Lehmann, Thomas A1 - Lenz, Ralf A1 - Morsi, Antonio A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Willert, Bernhard T1 - Computational results for validation of nominations T2 - Evaluating Gas Network Capacities N2 - The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances. Y1 - 2015 SN - 9781611973686 VL - SIAM-MOS series on Optimization ER - TY - CHAP A1 - Hayn, Christine A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Schewe, Lars A1 - Schweiger, Jonas A1 - Spreckelsen, Klaus T1 - Perspectives T2 - Evaluating Gas Network Capacities N2 - After we discussed approaches to validate nominations and to verify bookings, we consider possible future research paths. This includes determining technical capacities and planning of network extensions. Y1 - 2015 SN - 9781611973686 VL - SIAM-MOS series on Optimization ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Szabo, Jacint T1 - Gas Network Topology Optimization for Upcoming Market Requirements T2 - International Conference on the European Energy Market (EEM) N2 - Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed. Y1 - 2011 U6 - https://doi.org/10.1109/EEM.2011.5953035 SP - 346 EP - 351 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Gollmer, Ralf A1 - Hayn, Christine A1 - Henrion, René A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Mirkov, Radoslava A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets JF - Energy Systems N2 - The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor were united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We discuss how these changing paradigms lead to new and challenging mathematical optimization problems. This includes the validation of nominations, that asks for the decision if the network’s capacity is sufficient to transport a specific amount of flow, the verification of booked capacities and the detection of available freely allocable capacities, and the topological extension of the network with new pipelines or compressors in order to increase its capacity. In order to solve each of these problems and to provide meaningful results for the practice, a mixture of different mathematical aspects have to be addressed, such as combinatorics, stochasticity, uncertainty, and nonlinearity. Currently, no numerical solver is available that can deal with such blended problems out-of-the-box. The main goal of our research is to develop such a solver, that moreover is able to solve instances of realistic size. In this article, we describe the main ingredients of our prototypical software implementations. Y1 - 2013 U6 - https://doi.org/10.1007/s12667-013-0099-8 VL - 5 IS - 3 SP - 449 EP - 473 PB - Springer Berlin Heidelberg CY - Berlin ER -