@inproceedings{MartinGeisslerHeynetal.2011, author = {Martin, Alexander and Geißler, Bj{\"o}rn and Heyn, Christine and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Steinbach, Marc and Willert, Bernhard}, title = {Optimierung Technischer Kapazit{\"a}ten in Gasnetzen}, booktitle = {Optimierung in der Energiewirtschaft}, publisher = {VDI-Verlag, D{\"u}sseldorf}, pages = {105 -- 114}, year = {2011}, language = {en} } @misc{HillerSaitenmacherWalther2016, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61092}, year = {2016}, abstract = {We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model.}, language = {en} } @article{GamrathKochMaheretal.2017, author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, volume = {9}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-016-0114-x}, pages = {231 -- 296}, year = {2017}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.}, language = {en} } @misc{HillerWalther2018, author = {Hiller, Benjamin and Walther, Tom}, title = {Improving branching for disjunctive polyhedral models using approximate convex decompositions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67462}, year = {2018}, abstract = {Disjunctive sets arise in a variety of optimization models and much esearch has been devoted to obtain strong relaxations for them. This paper focuses on the evaluation of the relaxation during the branch-and-bound search process. We argue that the branching possibilities (\ie binary variables) of the usual formulations are unsuitable to obtain strong bounds early in the search process as they do not capture the overall shape of the the entire disjunctive set. To analyze and exploit the shape of the disjunctive set we propose to compute a hierarchy of approximate convex decompositions and show how to extend the known formulations to obtain improved branching behavior.}, language = {en} } @article{GriewankHasenfelderRadonsetal.2018, author = {Griewank, Andreas and Hasenfelder, Richard and Radons, Manuel and Lehmann, Lutz and Streubel, Tom}, title = {Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation}, volume = {33}, journal = {Optimization Methods and Software}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1378653}, pages = {1089 -- 1107}, year = {2018}, abstract = {In this article we analyse a generalized trapezoidal rule for initial value problems with piecewise smooth right-hand side F : IR^n -> IR^n based on a generalization of algorithmic differentiation. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a nondifferentiability of F. The advantage of the proposed generalized trapezoidal rule is threefold: Firstly, we can achieve a higher convergence order than with the classical method. Moreover, the method is energy preserving for piecewise linear Hamiltonian systems. Finally, in analogy to the classical case we derive a third-order interpolation polynomial for the numerical trajectory. In the smooth case, the generalized rule reduces to the classical one. Hence, it is a proper extension of the classical theory. An error estimator is given and numerical results are presented.}, language = {en} } @article{GriewankStreubelLehmannetal.2018, author = {Griewank, Andreas and Streubel, Tom and Lehmann, Lutz and Radons, Manuel and Hasenfelder, Richard}, title = {Piecewise linear secant approximation via algorithmic piecewise differentiation}, volume = {33}, journal = {Optimization Methods and Software}, number = {4-6}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1387256}, pages = {1108 -- 1126}, year = {2018}, abstract = {It is shown how piecewise differentiable functions F : IR^n -> IR^m that are defined by evaluation programmes can be approximated locally by a piecewise linear model based on a pair of sample points \check x and \hat x. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x - \check x||*||x - \hat x||). As an application of the piecewise linearization procedure we devise a generalized Newton's method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equalling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods.}, language = {en} } @article{SchweigerLiers2018, author = {Schweiger, Jonas and Liers, Frauke}, title = {A Decomposition Approach for Optimal Gas Network Extension with a Finite Set of Demand Scenarios}, volume = {19}, journal = {Optimization and Engineering}, number = {2}, publisher = {Springer}, pages = {297 -- 326}, year = {2018}, abstract = {Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the arising challenging optimization tasks. In fact, each subproblem consists of a mixed-integer nonlinear optimization problem (MINLP). Valid bounds on the objective value are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. Results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time.}, language = {en} } @article{HillerKochScheweetal.2018, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, volume = {270}, journal = {European Journal of Operational Research}, number = {3}, pages = {797 -- 808}, year = {2018}, abstract = {In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now trans- ported by independent 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 the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.}, language = {en} } @inproceedings{StreubelStrohmTrunschkeetal.2018, author = {Streubel, Tom and Strohm, Christian and Trunschke, Philipp and Tischendorf, Caren}, title = {Generic Construction and Efficient Evaluation of Network DAEs and Their Derivatives in the Context of Gas Networks}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, isbn = {978-3-319-89920-6}, doi = {10.1007/978-3-319-89920-6_83}, pages = {627 -- 632}, year = {2018}, abstract = {We present a concept that provides an efficient description of differential-algebraic equations (DAEs) describing flow networks which provides the DAE function f and their Jacobians in an automatized way such that the sparsity pattern of the Jacobians is determined before their evaluation and previously determined values of f can be exploited. The user only has to provide the network topology and local function descriptions for each network element. The approach uses automatic differentiation (AD) and is adapted to switching element functions via the abs-normal-form (ANF).}, language = {en} } @inproceedings{HoppmannSchwarz2018, author = {Hoppmann, Kai and Schwarz, Robert}, title = {Finding Maximum Minimum Cost Flows to Evaluate Gas Network Capacities}, booktitle = {Operations Research Proceedings 2017}, isbn = {978-3-319-89919-0}, doi = {10.1007/978-3-319-89920-6_46}, pages = {339 -- 346}, year = {2018}, abstract = {In this article we consider the following problem arising in the context of scenario generation to evaluate the transport capacity of gas networks: In the Uncapacitated Maximum Minimum Cost Flow Problem (UMMCF) we are given a flow network where each arc has an associated nonnegative length and infinite capacity. Additionally, for each source and each sink a lower and an upper bound on its supply and demand are known, respectively. The goal is to find values for the supplies and demands respecting these bounds, such that the optimal value of the induced Minimum Cost Flow Problem is maximized, i.e., to determine a scenario with maximum transportmoment. In this article we propose two linear bilevel optimization models for UMMCF, introduce a greedy-style heuristic, and report on our first computational experiment.}, language = {en} } @inproceedings{Hennings2018, author = {Hennings, Felix}, title = {Benefits and Limitations of Simplified Transient Gas Flow Formulations}, volume = {Operations Research Proceedings}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer, Cham}, doi = {10.1007/978-3-319-89920-6_32}, pages = {231 -- 237}, year = {2018}, abstract = {Although intensively studied in recent years, the optimization of the transient (time-dependent) control of large real-world gas networks is still out of reach for current state-of-the-art approaches. For this reason, we present further simplifications of the commonly used model, which lead to a linear description of the gas flow on pipelines. In an empirical analysis of real-world data, we investigate the properties of the involved quantities and evaluate the errors made by our simplification.}, language = {en} } @misc{LenzSchwarz2016, author = {Lenz, Ralf and Schwarz, Robert}, title = {Optimal Looping of Pipelines in Gas Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61564}, year = {2016}, abstract = {In this paper, we compare several approaches for the problem of gas network expansions using loops, that is, to build new pipelines in parallel to existing ones. We present different model formulations for the problem of continuous loop expansions as well as discrete loop expansions. We then analyze problem properties, such as the structure and convexity of the underlying feasible regions. The paper concludes with a computational study comparing the continuous and the discrete formulations.}, language = {en} } @misc{HennigSchwarz2016, author = {Hennig, Kai and Schwarz, Robert}, title = {Using Bilevel Optimization to find Severe Transport Situations in Gas Transmission Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61519}, year = {2016}, abstract = {In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib.}, language = {en} } @article{HumpolaFuegenschuh2015, author = {Humpola, Jesco and F{\"u}genschuh, Armin}, title = {Convex reformulations for solving a nonlinear network design problem}, volume = {62}, journal = {Computational Optimization and Applications}, number = {3}, publisher = {Springer US}, doi = {10.1007/s10589-015-9756-2}, pages = {717 -- 759}, year = {2015}, abstract = {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.}, language = {en} } @incollection{HaynHumpolaKochetal.2015, author = {Hayn, Christine and Humpola, Jesco and Koch, Thorsten and Schewe, Lars and Schweiger, Jonas and Spreckelsen, Klaus}, title = {Perspectives}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, year = {2015}, abstract = {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.}, language = {en} } @misc{Szabo2012, author = {Szab{\´o}, J{\´a}cint}, title = {The set of solutions to nomination validation in passive gas transportation networks with a generalized flow formula}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15151}, year = {2012}, abstract = {In this paper we give an analytical description on the structure of solutions to the gas nomination validation problem in gas transportation networks. These networks are assumed to contain no active devices, only certain hypothetical pipelines, where the flow of gas is modeled by a generalized version of the quadratic Weymouth's equation. The purpose of considering generalized flow formulas is to be able to adapt our results to various gas network optimization problems involving gas flow formulas beyond Weymouth's equation. Such formulas can appear in leaves of branch and bound trees, or they can stem from discretization and linearization carried out at active devices. We call a balanced supply-demand vector a nomination, and the passive nomination validation problem is to decide whether there exist pressures at the nodes generating a given nomination. We prove that in our setup the pressure square vectors generating a given nomination form a one-dimensional connected and continuous curve in the pressure square space, and this curve is a line for the classical Weymouth's equation. We also present a visual approach for the easy comprehension of how this solution curve arises; we give a short investigation of the set of feasible nominations; and finally we give a proof that the nomination validation problem in gas networks with active devices is NP-complete.}, language = {en} } @misc{MartinGeisslerHaynetal.2012, author = {Martin, Alexander and Geißler, Bj{\"o}rn and Hayn, Christine and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Steinbach, Marc and Willert, Bernhard}, title = {Optimierung Technischer Kapazit{\"a}ten in Gasnetzen}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15121}, year = {2012}, abstract = {Die mittel- und l{\"a}ngerfristige Planung f{\"u}r den Gastransport hat sich durch {\"A}nderungen in den regulatorischen Rahmenbedingungen stark verkompliziert. Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel diskutiert die hieraus resultierenden mathematischen Planungsprobleme, welche als Validierung von Nominierungen und Buchungen, Bestimmung der technischen Kapazit{\"a}t und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und L{\"o}sungsans{\"a}tze skizziert.}, language = {de} } @misc{HillerKochScheweetal.2018, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67438}, year = {2018}, abstract = {In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now transported by independent 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 the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.}, language = {en} } @misc{BennerGrundelHimpeetal.2017, author = {Benner, Peter and Grundel, Sara and Himpe, Christian and Huck, Christoph and Streubel, Tom and Tischendorf, Caren}, title = {Gas Network Benchmark Models}, issn = {1438-0064}, doi = {10.1007/11221_2018_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66274}, year = {2017}, abstract = {The simulation of gas transportation networks becomes increasingly more important as its use-cases broadens to more complex applications. Classically, the purpose of the gas network was the transportation of predominantly natural gas from a supplier to the consumer for long-term scheduled volumes. With the rise of renewable energy sources, gas-fired power plants are often chosen to compensate for the fluctuating nature of the renewables, due to their on-demand power generation capability. Such an only short-term plannable supply and demand setting requires sophisticated simulations of the gas network prior to the dispatch to ensure the supply of all customers for a range of possible scenarios and to prevent damages to the gas network. In this work we describe the modelling of gas networks and present benchmark systems to test implementations and compare new or extended models.}, language = {en} } @misc{GriewankHasenfelderRadonsetal.2017, author = {Griewank, Andreas and Hasenfelder, Richard and Radons, Manuel and Lehmann, Lutz and Streubel, Tom}, title = {Integrating Lipschitzian Dynamical Systems using Piecewise Algorithmic Differentiation}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1378653}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64639}, year = {2017}, abstract = {In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side \(F:R^n \to R^n\) based on a generalization of algorithmic differentiation. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a nondifferentiability of \(F\). The advantage of the proposed generalized trapezoidal rule is threefold: Firstly, we can achieve a higher convergence order than with the classical method. Moreover, the method is energy preserving for piecewise linear Hamiltonian systems. Finally, in analogy to the classical case we derive a third order interpolation polynomial for the numerical trajectory. In the smooth case the generalized rule reduces to the classical one. Hence, it is a proper extension of the classical theory. An error estimator is given and numerical results are presented.}, language = {en} } @misc{Hennings2017, author = {Hennings, Felix}, title = {Benefits and Limitations of Simplified Transient Gas Flow Formulations}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_32}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64570}, year = {2017}, abstract = {Although intensively studied in recent years, the optimization of the transient (time-dependent) control of large real-world gas networks is still out of reach for current state-of-the-art approaches. For this reason, we present further simplifications of the commonly used model, which lead to a linear description of the gas flow on pipelines. In an empirical analysis of real-world data, we investigate the properties of the involved quantities and evaluate the errors made by our simplification.}, language = {en} } @misc{StreubelStrohmTrunschkeetal.2017, author = {Streubel, Tom and Strohm, Christian and Trunschke, Philipp and Tischendorf, Caren}, title = {Generic Construction and Efficient Evaluation of Network DAEs and Their Derivatives in the Context of Gas Networks}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_83}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64582}, year = {2017}, abstract = {We present a concept that provides an efficient description of differential-algebraic equations (DAEs) describing flow networks which provides the DAE function f and their Jacobians in an automatized way such that the sparsity pattern of the Jacobians is determined before their evaluation and previously determined values of f can be exploited. The user only has to provide the network topology and local function descriptions for each network element. The approach uses automatic differentiation (AD) and is adapted to switching element functions via the abs-normal-form (ANF).}, language = {en} } @incollection{BargmannEbbersHeineckeetal.2015, author = {Bargmann, Dagmar and Ebbers, Mirko and Heinecke, Nina and Koch, Thorsten and K{\"u}hl, Veronika and Pelzer, Antje and Pfetsch, Marc and R{\"o}vekamp, Jessica and Spreckelsen, Klaus}, title = {State-of-the-art in evaluating gas network capacities}, booktitle = {Evaluating Gas Network Capacities}, publisher = {Society for Industrial and Applied Mathematics}, isbn = {9781611973686}, pages = {65 -- 84}, year = {2015}, language = {en} }