Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics
Hennings, Felix1 orcid ; Hoppmann-Baum, Kai2 orcid ; Zittel, Janina2 orcid
1Technische Universität Berlin Chair of Software and Algorithms for Discrete Optimization Straße des 17. Juni 135, 10623 Berlin, Germany
2Zuse Institute Berlin Applied Algorithmic Intelligence Methods Department Takustraße 7, 14195 Berlin, Germany
Open Journal of Mathematical Optimization, Tome 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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
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

Hennings, Felix  1   ; Hoppmann-Baum, Kai  2   ; Zittel, Janina  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
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{OJMO_2024__5__A1_0,
     author = {Hennings, Felix and Hoppmann-Baum, Kai and Zittel, Janina},
     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},
     year = {2024},
     publisher = {Universit\'e de Montpellier},
     volume = {5},
     doi = {10.5802/ojmo.29},
     zbl = {07893307},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/ojmo.29/}
}
TY  - JOUR
AU  - Hennings, Felix
AU  - Hoppmann-Baum, Kai
AU  - Zittel, Janina
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://www.numdam.org/articles/10.5802/ojmo.29/
DO  - 10.5802/ojmo.29
LA  - en
ID  - OJMO_2024__5__A1_0
ER  - 
%0 Journal Article
%A Hennings, Felix
%A Hoppmann-Baum, Kai
%A Zittel, Janina
%T Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics
%J Open Journal of Mathematical Optimization
%] 1
%D 2024
%P 1-34
%V 5
%I Université de Montpellier
%U https://www.numdam.org/articles/10.5802/ojmo.29/
%R 10.5802/ojmo.29
%G en
%F OJMO_2024__5__A1_0
Hennings, Felix; Hoppmann-Baum, Kai; Zittel, Janina. Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics. Open Journal of Mathematical Optimization, Tome 5 (2024), article  no. 1, 34 p.. doi: 10.5802/ojmo.29

[1] Adelhütte, Dennis; Aßmann, Denis; Grandòn, Tatiana Gonzàlez; Gugat, Martin; Heitsch, Holger; Henrion, René; Liers, Frauke; Nitsche, Sabrina; Schultz, Rüdiger; Stingl, Michael; Wintergerst, David 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] Berthold, Timo; Hendel, Gregor; Koch, Thorsten From Feasibility to Improvement to Proof: Three Phases of Solving Mixed-Integer Programs, Optim. Methods Softw., Volume 33 (2018) no. 3, pp. 499-517 | Zbl | DOI | MR

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

[4] Boland, Natachia; Ernst, Andreas; Kalinowski, T.; Rocha de Paula, Mateus; Savelsbergh, Martin; Singh, Gaurav 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] Bonami, Pierre; Lodi, Andrea; Tramontani, Andrea; Wiese, Sven On Mathematical Programming with Indicator Constraints, Math. Program., Volume 151 (2015) no. 1, pp. 191-223 | DOI | MR | Zbl

[6] Burlacu, Robert; Egger, Herbert; Groß, Martin; Martin, Alexander; Pfetsch, Marc E.; Schewe, Lars; Sirvent, Mathias; Skutella, Martin 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] Capitanescu, Florin 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] Domschke, Pia; Geißler, Björn; Kolb, Oliver; Lang, Jens; Martin, Alexander; Morsi, Antonio 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] Domschke, Pia; Hiller, Benjamin; Lang, Jens; Mehrmann, Volker; Morandin, Riccardo; Tischendorf, Caren Gas Network Modeling: An Overview (2021) (Technical Report)

[10] Domschke, Pia; Kolb, Oliver; Lang, Jens 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] Fügenschuh, Armin; Geißler, Björn; Gollmer, Ralf; Morsi, Antonio; Pfetsch, Marc E.; Rövekamp, Jessica; Schmidt, Martin; Spreckelsen, Klaus; Steinbach, Marc C. Physical and Technical Fundamentals of Gas Networks, Evaluating Gas Network Capacities (Koch, Thorsten; Hiller, Benjamin; Pfetsch, Marc E.; Schewe, Lars, 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] Glomb, Lukas; Liers, Frauke; Rösel, Florian A Rolling-Horizon Approach for Multi-Period Optimization, Eur. J. Oper. Res., Volume 300 (2022) no. 1, pp. 189-206 | DOI | MR | Zbl

[16] González Rueda, Ángel M.; González Díaz, Julio; Fernández de Córdoba, María P. 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] Gugat, Martin; Leugering, Günter; Martin, Alexander; Schmidt, Martin; Sirvent, Mathias; Wintergerst, David 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] Hahn, Mirko; Leyffer, Sven; Zavala, Victor M. Mixed-Integer PDE-Constrained Optimal Control of Gas Networks (2017) (Preprint)

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

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

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

[23] Hennings, Felix; Petkovic, Milena; Streubel, Tom 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] Hoppmann-Baum, Kai Mathematical Programming for Stable Control and Safe Operation of Gas Transport Networks, Ph. D. Thesis, Technische Universität Berlin (2022) | DOI

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

[26] Hoppmann-Baum, Kai; Hennings, Felix; Zittel, Janina; Gotzes, Uwe; Spreckelsen, Eva-Maria; Spreckelsen, Klaus; Koch, Thorsten 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 (Koch, Thorsten; Hiller, Benjamin; Pfetsch, Marc E.; Schewe, Lars, eds.), MOS-SIAM Series on Optimization, 21, Society for Industrial and Applied Mathematics, 2015 | DOI | Zbl

[28] Kolb, Oliver; Lang, Jens; Bales, Pia 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] Lenz, Ralf Optimization of Stationary Expansion Planning and Transient Network Control by Mixed-Integer Nonlinear Programming, Ph. D. Thesis, Technische Universität Berlin (2021) | DOI

[30] Mahlke, Debora; Martin, Alexander; Moritz, Susanne 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] Moritz, Susanne A Mixed Integer Approach for the Transient Case of Gas Network Optimization, Doctoral Thesis, Technische Universität Darmstadt (2007)

[32] Newman, Alexandra M.; Kuchta, Mark 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] Nikuradse, Johann 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] Osiadacz, Andrej J. Different Transient Flow Models - Limitations, Advantages, And Disadvantages, PSIG Annual Meeting, Pipeline Simulation Interest Group (1996) (PSIG-9606)

[36] Pápay, J. 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] Pfetsch, Marc E.; Fügenschuh, Armin; Geißler, Björn; Geißler, Nina; Gollmer, Ralf; Hiller, Benjamin; Humpola, Jesco; Koch, Thorsten; Lehmann, Thomas; Martin, Alexander; Morsi, Antonio; Rövekamp, Jessica; Schewe, Lars; Schmidt, Martin; Schultz, Rüdiger; Schwarz, Robert; Schweiger, Jonas; Stangl, Claudia; Steinbach, Marc C.; Vigerske, Stefan; Willert, Bernhard M. 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] Takacs, Gabor Comparing Methods for Calculating Z-factor, Oil Gas J., Volume 87 (1989) no. 20, pp. 43-46

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

[41] Tiacci, Lorenzo; Saetta, Stefano 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] Wächter, Andreas; Biegler, Lorenz T. 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] Walther, Tom; Hiller, Benjamin Modelling Compressor Stations in Gas Networks (2017) no. 17-67 (ZIB-Report)

Cité par Sources :