Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics
Open Journal of Mathematical Optimization, Volume 5 (2024), article no. 1, 34 p.

Optimizing the transient control of gas networks is a highly challenging task. The corresponding model incorporates the combinatorial complexity of determining the settings for the many active elements as well as the non-linear and non-convex nature of the physical and technical principles of gas transport. In this paper, we present the latest improvements of our ongoing work to tackle this problem for real-world, large-scale problem instances: By adjusting our mixed-integer non-linear programming model regarding the gas compression capabilities in the network, we reflect the technical limits of the underlying units more accurately while maintaining a similar overall model size. In addition, we introduce a new algorithmic approach that is based on splitting the complexity of the problem by first finding assignments for discrete variables and then determining the continuous variables as locally optimal solution of the corresponding non-linear program. For the first task, we design multiple different heuristics based on concepts for general time-expanded optimization problems that find solutions by solving a sequence of sub-problems defined on reduced time horizons. To demonstrate the competitiveness of our approach, we test our algorithm on particularly challenging historical demand scenarios. The results show that high-quality solutions are obtained reliably within short run times, making the algorithm well-suited to be applied at the core of time-critical industrial applications.

Published online:
DOI: 10.5802/ojmo.29
Keywords: Transient Gas Network Optimization, Sequential Mixed-Integer Programming, Rolling Horizon Heuristic, Aggregated Horizon Heuristic, Real-World Historical Instances, Industry-Ready
Felix Hennings 1; Kai Hoppmann-Baum 2; Janina Zittel 2

1 Technische Universität Berlin Chair of Software and Algorithms for Discrete Optimization Straße des 17. Juni 135, 10623 Berlin, Germany
2 Zuse Institute Berlin Applied Algorithmic Intelligence Methods Department Takustraße 7, 14195 Berlin, Germany
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
     author = {Felix Hennings and Kai Hoppmann-Baum and Janina Zittel},
     title = {Optimizing transient gas network control for challenging real-world instances using {MIP-based} heuristics},
     journal = {Open Journal of Mathematical Optimization},
     eid = {1},
     pages = {1--34},
     publisher = {Universit\'e de Montpellier},
     volume = {5},
     year = {2024},
     doi = {10.5802/ojmo.29},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.29/}
AU  - Felix Hennings
AU  - Kai Hoppmann-Baum
AU  - Janina Zittel
TI  - Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics
JO  - Open Journal of Mathematical Optimization
PY  - 2024
SP  - 1
EP  - 34
VL  - 5
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.29/
DO  - 10.5802/ojmo.29
LA  - en
ID  - OJMO_2024__5__A1_0
ER  - 
%0 Journal Article
%A Felix Hennings
%A Kai Hoppmann-Baum
%A Janina Zittel
%T Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics
%J Open Journal of Mathematical Optimization
%D 2024
%P 1-34
%V 5
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.29/
%R 10.5802/ojmo.29
%G en
%F OJMO_2024__5__A1_0
Felix Hennings; Kai Hoppmann-Baum; Janina Zittel. Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics. Open Journal of Mathematical Optimization, Volume 5 (2024), article  no. 1, 34 p. doi : 10.5802/ojmo.29. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.29/

[1] Dennis Adelhütte; Denis Aßmann; Tatiana Gonzàlez Grandòn; Martin Gugat; Holger Heitsch; René Henrion; Frauke Liers; Sabrina Nitsche; Rüdiger Schultz; Michael Stingl; David Wintergerst Joint Model of Probabilistic-Robust (Probust) Constraints Applied to Gas Network Optimization, Vietnam J. Math., Volume 49 (2021) no. 4, pp. 1097-1130 | DOI | MR | Zbl

[2] Timo Berthold; Gregor Hendel; Thorsten Koch From Feasibility to Improvement to Proof: Three Phases of Solving Mixed-Integer Programs, Optim. Methods Softw., Volume 33 (2018) no. 3, pp. 499-517 | DOI | MR | Zbl

[3] Ksenia Bestuzheva; Mathieu Besançon; Wei-Kun Chen; Antonia Chmiela; Tim Donkiewicz; Jasper van Doornmalen; Leon Eifler; Oliver Gaul; Gerald Gamrath; Ambros Gleixner; Leona Gottwald; Christoph Graczyk; Katrin Halbig; Alexander Hoen; Christopher Hojny; Rolf van der Hulst; Thorsten Koch; Marco Lübbecke; Stephen J. Maher; Frederic Matter; Erik Mühmer; Benjamin Müller; Marc E. Pfetsch; Daniel Rehfeldt; Steffan Schlein; Franziska Schlösser; Felipe Serrano; Yuji Shinano; Boro Sofranac; Mark Turner; Stefan Vigerske; Fabian Wegscheider; Philipp Wellner; Dieter Weninger; Jakob Witzig The SCIP Optimization Suite 8.0 (2021) no. 21-41 (ZIB-Report)

[4] Natachia Boland; Andreas Ernst; T. Kalinowski; Mateus Rocha de Paula; Martin Savelsbergh; Gaurav Singh Time Aggregation for Network Design to Meet Time-Constrained Demand, MODSIM 2013: 20th International Congress on Modelling and Simulation - Adapting to Change: The Multiple Roles of Modelling, Modelling and Simulation Society of Australia and New Zealand (2013), pp. 3281-3287

[5] Pierre Bonami; Andrea Lodi; Andrea Tramontani; Sven Wiese On Mathematical Programming with Indicator Constraints, Math. Program., Volume 151 (2015) no. 1, pp. 191-223 | DOI | MR | Zbl

[6] Robert Burlacu; Herbert Egger; Martin Groß; Alexander Martin; Marc E. Pfetsch; Lars Schewe; Mathias Sirvent; Martin Skutella Maximizing the Storage Capacity of Gas Networks: A Global MINLP Approach, Optim. Eng., Volume 20 (2019) no. 2, pp. 543-573 | DOI | MR | Zbl

[7] Florin Capitanescu A Relax and Reduce Sequential Decomposition Rolling Horizon Algorithm to Value Dynamic Network Reconfiguration in Smart Distribution Grid, 2017 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT-Europe) (2017), pp. 1-6 | DOI

[8] Pia Domschke; Björn Geißler; Oliver Kolb; Jens Lang; Alexander Martin; Antonio Morsi Combination of Nonlinear and Linear Optimization of Transient Gas Networks, INFORMS J. Comput., Volume 23 (2011) no. 4, pp. 605-617 | DOI | MR | Zbl

[9] Pia Domschke; Benjamin Hiller; Jens Lang; Volker Mehrmann; Riccardo Morandin; Caren Tischendorf Gas Network Modeling: An Overview (2021) (Technical Report)

[10] Pia Domschke; Oliver Kolb; Jens Lang Fast and Reliable Transient Simulation and Continuous Optimization of Large-Scale Gas Networks, Math. Methods Oper. Res., Volume 95 (2022) no. 3, pp. 475-501 | DOI | MR | Zbl

[11] Federal Ministry for Economic Affairs and Climate Action KfW, Gasunie and RWE Sign MoU to Build an LNG Terminal at Brunsbüttel, https://www.bmwi.de/Redaktion/EN/Pressemitteilungen/2022/03/202203-kfw-gasunie-and-rwe-sign-mou-to-build-an-lng-terminal-at-brunsbuettel.html, 2022 (Accessed: 2022-03-24)

[12] FNB Gas – Association of German transmission system operators Scenario Framework Gas Network Development Plan 2022–2032, https://fnb-gas.de/en/scenario-framework/scenario-framework-2022/, 2021 (Accessed: 2022-03-24)

[13] Armin Fügenschuh; Björn Geißler; Ralf Gollmer; Antonio Morsi; Marc E. Pfetsch; Jessica Rövekamp; Martin Schmidt; Klaus Spreckelsen; Marc C. Steinbach Physical and Technical Fundamentals of Gas Networks, Evaluating Gas Network Capacities (Thorsten Koch; Benjamin Hiller; Marc E. Pfetsch; Lars Schewe, eds.) (MOS-SIAM Series on Optimization), Volume 21, Society for Industrial and Applied Mathematics, 2015

[14] GAMS Development Corporation General Algebraic Modeling System (GAMS) Release 38.1.0, Fairfax, VA, USA, 2022

[15] Lukas Glomb; Frauke Liers; Florian Rösel A Rolling-Horizon Approach for Multi-Period Optimization, Eur. J. Oper. Res., Volume 300 (2022) no. 1, pp. 189-206 | DOI | MR | Zbl

[16] Ángel M. González Rueda; Julio González Díaz; María P. Fernández de Córdoba A Twist on SLP Algorithms for NLP and MINLP Problems: An Application to Gas Transmission Networks, Optim. Eng., Volume 20 (2019) no. 2, pp. 349-395 | DOI | MR | Zbl

[17] Martin Gugat; Günter Leugering; Alexander Martin; Martin Schmidt; Mathias Sirvent; David Wintergerst MIP-Based Instantaneous Control of Mixed-Integer PDE-Constrained Gas Transport Problems, Comput. Optim. Appl., Volume 70 (2018) no. 1, pp. 267-294 | DOI | MR | Zbl

[18] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, Version 9.5, https://www.gurobi.com, 2021 (Accessed: 2022-03-24)

[19] Mirko Hahn; Sven Leyffer; Victor M. Zavala Mixed-Integer PDE-Constrained Optimal Control of Gas Networks (2017) (Preprint)

[20] Felix Hennings Benefits and Limitations of Simplified Transient Gas Flow Formulations, Operations Research Proceedings 2017, Springer, 2018, pp. 231-237 | DOI

[21] Felix Hennings Large-Scale Empirical Study on the Momentum Equation’s Inertia Term, J. Nat. Gas Sci. Eng., Volume 95 (2021), 104153 | DOI

[22] Felix Hennings; Lovis Anderson; Kai Hoppmann-Baum; Mark Turner; Thorsten Koch Controlling Transient Gas Flow in Real-World Pipeline Intersection Areas, Optim. Eng., Volume 22 (2021) no. 2, pp. 687-734 | DOI

[23] Felix Hennings; Milena Petkovic; Tom Streubel On the Numerical Treatment of Interlaced Target Values - Modeling, Optimization and Simulation of Regulating Valves in Gas Networks (2021) no. 21-32 (ZIB-Report)

[24] Kai Hoppmann-Baum Mathematical Programming for Stable Control and Safe Operation of Gas Transport Networks, Ph. D. Thesis, Technische Universität Berlin (2022) | DOI

[25] Kai Hoppmann-Baum; Felix Hennings; Ralf Lenz; Uwe Gotzes; Nina Heinecke; Klaus Spreckelsen; Thorsten Koch Optimal Operation of Transient Gas Transport Networks, Optim. Eng., Volume 22 (2021) no. 2, pp. 735-781 | DOI | MR | Zbl

[26] Kai Hoppmann-Baum; Felix Hennings; Janina Zittel; Uwe Gotzes; Eva-Maria Spreckelsen; Klaus Spreckelsen; Thorsten Koch From Natural Gas towards Hydrogen - A Feasibility Study on Current Transport Network Infrastructure and Its Technical Control (2020) no. 20-27 (ZIB-Report)

[27] Evaluating Gas Network Capacities (Thorsten Koch; Benjamin Hiller; Marc E. Pfetsch; Lars Schewe, eds.), MOS-SIAM Series on Optimization, 21, Society for Industrial and Applied Mathematics, 2015 | DOI | Zbl

[28] Oliver Kolb; Jens Lang; Pia Bales An Implicit Box Scheme for Subsonic Compressible Flow with Dissipative Source Term, Numer. Algorithms, Volume 53 (2010) no. 2, pp. 293-307 | DOI | MR | Zbl

[29] Ralf Lenz Optimization of Stationary Expansion Planning and Transient Network Control by Mixed-Integer Nonlinear Programming, Ph. D. Thesis, Technische Universität Berlin (2021) | DOI

[30] Debora Mahlke; Alexander Martin; Susanne Moritz A Simulated Annealing Algorithm for Transient Optimization in Gas Networks, Math. Methods Oper. Res., Volume 66 (2007) no. 1, pp. 99-115 | DOI | MR | Zbl

[31] Susanne Moritz A Mixed Integer Approach for the Transient Case of Gas Network Optimization, Doctoral Thesis, Technische Universität Darmstadt (2007)

[32] Alexandra M. Newman; Mark Kuchta Using Aggregation to Optimize Long-Term Production Planning at an Underground Mine, Eur. J. Oper. Res., Volume 176 (2007) no. 2, pp. 1205-1218 | DOI | Zbl

[33] Johann Nikuradse Laws of Flow in Rough Pipes, National Advisory Committee for Aeronautics Washington, 1950

[34] Open Grid Europe GmbH, https://oge.net/en (Accessed: 2022-03-24)

[35] Andrej J. Osiadacz Different Transient Flow Models - Limitations, Advantages, And Disadvantages, PSIG Annual Meeting, Pipeline Simulation Interest Group (1996) (PSIG-9606)

[36] J. Pápay A Termeléstechnológiai Paraméterek Változása a Gáztelepek Müvelése Során, OGIL Müsz. Tud. Közl. (1968), pp. 267-273

[37] Marc E. Pfetsch; Armin Fügenschuh; Björn Geißler; Nina Geißler; Ralf Gollmer; Benjamin Hiller; Jesco Humpola; Thorsten Koch; Thomas Lehmann; Alexander Martin; Antonio Morsi; Jessica Rövekamp; Lars Schewe; Martin Schmidt; Rüdiger Schultz; Robert Schwarz; Jonas Schweiger; Claudia Stangl; Marc C. Steinbach; Stefan Vigerske; Bernhard M. Willert Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions, Optim. Methods Softw., Volume 30 (2015) no. 1, pp. 15-53 | DOI | MR | Zbl

[38] Plotly Technologies Inc. Collaborative Data Science, https://plotly.com, 2015 (Accessed: 2022-03-24)

[39] Gabor Takacs Comparing Methods for Calculating Z-factor, Oil Gas J., Volume 87 (1989) no. 20, pp. 43-46

[40] Till Tantau The TikZ and PGF Packages - Manual for Version 3.1.9a, https://github.com/pgf-tikz/pgf, 2021 (Accessed: 2022-03-24)

[41] Lorenzo Tiacci; Stefano Saetta Demand Forecasting, Lot Sizing and Scheduling on a Rolling Horizon Basis, Int. J. Prod. Econ., Volume 140 (2012) no. 2, pp. 803-814 | DOI

[42] Andreas Wächter; Lorenz T. Biegler On the Implementation of an Interior-Point Filter Line-Search Algorithm for Large-Scale Nonlinear Programming, Math. Program., Volume 106 (2006) no. 1, pp. 25-57 | DOI | MR | Zbl

[43] Tom Walther; Benjamin Hiller Modelling Compressor Stations in Gas Networks (2017) no. 17-67 (ZIB-Report)

Cited by Sources: