TY - INPR A1 - Schmidt, Martin A1 - Hiller, Benjamin A1 - Koch, Thorsten A1 - Pfetsch, Marc A1 - Geißler, Björn A1 - Henrion, René A1 - Joormann, Imke A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Schewe, Lars A1 - Schultz, Rüdiger A1 - Steinbach, Marc C. T1 - Capacity Evaluation for Large-Scale Gas Networks N2 - Natural gas is important for the energy turnaround in many countries like in Germany, where it serves as a "bridging energy" towards a fossil-free energy supply in the future. About 20% of the total German energy demand is provided by natural gas, which is transported through a complex pipeline network with a total length of about 30000 km and the efficient use of the given transport infrastructure for natural gas is of political, economic, and societal importance. As a consequence of the liberalization of the European gas market in the last decades, gas trading and transport have been decoupled. This has led to new challenges for gas transport companies, and mathematical optimization is perfectly suited for tackling many of these challenges. However, the underlying mathematical problems are by far too hard to be solved by today's general-purpose software so that novel mathematical theory and algorithms are needed. The industrial research project "ForNe: Research Cooperation Network Optimization" has been initiated and funded by Open Grid Europe in 2009 and brought together experts in mathematical optimization from seven German universities and research institutes, which cover almost the entire range of mathematical optimization: integer and nonlinear optimization as well as optimization under uncertainty. The mathematical research results have been put together in a software package that has been delivered to Open Grid Europe at the end of the project. Moreover, the research is still continuing - e.g., in the Collaborative Research Center/Transregio 154 "Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks" funded by the German Research Foundation. Y1 - 2019 ER - TY - INPR A1 - Klimm, Max A1 - Pfetsch, Marc E. A1 - Raber, Rico A1 - Skutella, Martin T1 - Packing under Convex Quadratic Constraints N2 - We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX-hard to approximate and present constant-factor approximation algorithms based upon three different algorithmic techniques: (1) a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation whose approximation ratio equals the golden ratio; (2) a greedy strategy; (3) a randomized rounding method leading to an approximation algorithm for the more general case with multiple convex quadratic constraints. We further show that a combination of the first two strategies can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of the three algorithms for problem instances arising in the context of real-world gas transport networks. Y1 - 2019 ER - TY - INPR A1 - Klimm, Max A1 - Pfetsch, Marc A1 - Raber, Rico A1 - Skutella, Martin T1 - On the Robustness of Potential-Based Flow Networks N2 - Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., electricity, gas, or water networks, where the flow along each edge is controlled via the (difference of) potentials at its end nodes. A potential-based flow network is robust if the maximal difference of node potentials needed to satisfy a set of demands cannot increase if demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reservations for certain demands that may be larger than the actual amounts sent later on. Here node potentials correspond to physical quantities such as the pressures or the voltages and must be guaranteed to lie within a fixed range, even if the actual amounts are smaller than the previously reserved demands. Our main results are a precise characterization of such robust networks for the case of point-to-point demands via forbidden node-labeled graph minors, as well as an efficient algorithm for testing robustness. Y1 - 2019 ER - TY - INPR A1 - Habeck, Oliver A1 - Pfetsch, Marc E. T1 - Combinatorial Acyclicity Models for Potential-based Flows N2 - Potential-based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this paper is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables for flow directions. We compare these models and introduce a particular model that tries to capture acyclicity together with the supply/demand behavior. We analyze properties of this model, including variable fixing rules. Our computational results show that the usage of the corresponding constraints speeds up solution times by about a factor of 3 on average and a speed-up of a factor of almost 5 for the time to prove optimality. KW - Network Optimization KW - Potential networks KW - Potential-based flows KW - acyclic flows Y1 - 2020 ER - TY - INPR A1 - Klimm, Max A1 - Pfetsch, Marc A1 - Raber, Rico A1 - Skutella, Martin T1 - Approximation of Binary Second Order Cone Programs of Packing Type N2 - This paper considers binary second order cone programs of packing type where a linear objective is optimized under m second order cone packing constraints and all decision variables are binary. We show that when m is part of the input, these problems cannot be approximated within a factor of 1/(m + 1)^(1−ε) for any ε > 0, unless P = NP. We then propose approximation algorithms based on different algorithmic principles that almost match this approximation factor: a pipage rounding technique that solves fractional relaxations of the problems and modifies the solutions so that few fractional variables remain, a greedy approach, and a randomized rounding technique. While all algorithms have similar theoretical approximation guarantees in the order of 1/m, we also test the algorithms on realistic instances that arise in the context of gas transportation networks. This empirical study reveals in particular that taking the best of the proposed algorithms produces highly competitive solutions that yield on average 96 % of the value of an optimal solution. Y1 - 2021 ER - TY - INPR A1 - Klimm, Max A1 - Pfetsch, Marc A1 - Raber, Rico A1 - Skutella, Martin T1 - Reduction of Potential-Based Flow Networks N2 - We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties such as voltages or pressures are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks such as electricity, gas, or water networks. In contrast to Kron's reduction for electrical networks, we prove that, in general, potential-based flow networks with at least three terminals cannot be reduced to smaller networks whose size only depends on the number of terminals. On the other hand, we show that it is possible to represent a special class of potential-based flow networks by a complete graph on the terminals, and we establish a characterization of networks that can be reduced to a path network. Our results build on fundamental properties of effective resistances proved in this paper, including explicit formulae for their dependence on edge resistances of the network and their metric properties. Y1 - 2021 ER - TY - INPR A1 - Strubberg, Lea A1 - Lutz, Annette A1 - Börner, Pascal A1 - Pfetsch, Marc A1 - Skutella, Martin A1 - Klimm, Max T1 - Valid Cuts for the Design of Potential-based Flow Networks N2 - The construction of a cost minimal network for flows obeying physical laws is an important problem for the design of electricity, water, hydrogen, and natural gas infrastructures. We formulate this problem as a mixed-integer non-linear program. Its non-convexity, due to the poten- tial flow, together with the binary variables, indicating the decision to build a connection, make these problems challenging to solve. We develop a novel class of valid inequalities on the fractional relaxations of the bi- nary variables. Further, we show that this class of inequalities can be sep- arated in polynomial for solutions to a fractional relaxation. This makes it possible to incorporate these inequalities into a branch-and-bound al- gorithm. The advantage of these inequalities is lastly demonstrated in a computational study on the design of real-world gas transport networks. KW - potential based flows KW - topology optimization KW - MINLP Y1 - 2025 ER - TY - INPR A1 - Börner, Pascal A1 - Giesselmann, Jan A1 - Kumar, Varun M. A1 - Pfetsch, Marc E. A1 - Thiele, Michael A1 - Tscherpel, Tabea T1 - Gas Mixtures on Networks: Modeling, Simulation and Optimization N2 - This chapter addresses mathematical models for isothermal mixtures of hydrogen and natural gas, motivated by the need for reliable simulation tools in future low-carbon energy systems. We analyze several classes of mixture models and investigate their convergence properties in the regime of strong interaction between constituents, covering stationary and instationary single-pipe settings as well as network flows. Since mixture models critically depend on the choice of pressure law, we compare the industry-standard GERG equation of state with simplified alternatives that preserve convex energies and reduce computational costs. For network applications, we discuss consistent coupling conditions across model classes, explore optimization of steady flows using the algebraic Weymouth formulation, and provide numerical evidence for its applicability in relevant operating regimes. The study reveals when simplified models are justified and outlines key open challenges for the modeling of gas mixtures. Y1 - ER -