×

A system to evaluate gas network capacities: concepts and implementation. (English) Zbl 1403.90202

Summary: 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 is 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.

MSC:

90B10 Deterministic network models in operations research
90C11 Mixed integer programming
90C90 Applications of mathematical programming
91B76 Environmental economics (natural resource models, harvesting, pollution, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T., SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41, (2009) · Zbl 1171.90476
[2] Bargmann, D., Ebbers, M., Geißler, N., Koch, T., Kühl, V., Pelzer, A., Pfetsch, M. E., Rövekamp, J., & Spreckelsen, K. (2015). State of the art in evaluating gas network capacities. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Bargmann, D., Ebbers, M., Geißler, N., Koch, T., Kühl, V., Pelzer, A., Pfetsch, M. E., Rövekamp, J., & Spreckelsen, K. (2015). State of the art in evaluating gas network capacities. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693 · Zbl 1343.90050
[3] CherryPy - A minimalist python web framework. http://cherrypy.org/; CherryPy - A minimalist python web framework. http://cherrypy.org/
[4] Colson, B.; Marcotte, P.; Savard, G., An overview of bilevel optimization, Annals of Operations Research, 153, 1, 235-256, (2007) · Zbl 1159.90483
[5] Domschke, P.; Geißler, B.; Kolb, O.; Lang, J.; Martin, A.; Morsi, A., Combination of nonlinear and linear optimization of transient gas networks, INFORMS Journal on Computing, 23, 4, 605-617, (2011) · Zbl 1243.90030
[6] Fügenschuh, A., Geißler, B., Gollmer, R., Morsi, A., Pfetsch, M. E., Rövekamp, J., Schmidt, M., Spreckelsen, K., & Steinbach, M. C. (2015). Physical and technical fundamentals of gas networks. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Fügenschuh, A., Geißler, B., Gollmer, R., Morsi, A., Pfetsch, M. E., Rövekamp, J., Schmidt, M., Spreckelsen, K., & Steinbach, M. C. (2015). Physical and technical fundamentals of gas networks. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693
[7] Fügenschuh, A.; Hiller, B.; Humpola, J.; Koch, T.; Lehman, T.; Schwarz, R., Gas network topology optimization for upcoming market requirements, IEEE Proceedings of the Eighth International Conference on the European Energy Market (EEM), 2011, 346-351, (2011)
[8] GAMS. http://www.gams.com; GAMS. http://www.gams.com · Zbl 0915.90048
[9] Verordnung über den Zugang von Gasversorgungsnetzen (Gasnetzzugangsverordnung - GasNZV). Version released Sep. 03, 2010.; Verordnung über den Zugang von Gasversorgungsnetzen (Gasnetzzugangsverordnung - GasNZV). Version released Sep. 03, 2010.
[10] Geißler, B.; Martin, A.; Morsi, A.; Schewe, L., Using piecewise linear functions for solving minlps, (Lee, J.; Leyffer, S., Mixed integer nonlinear programming, The IMA Volumes in Mathematics and its Applications, 154, (2012), Springer New York), 287-314 · Zbl 1242.90132
[11] Geißler, B., Martin, A., Morsi, A., & Schewe, L. (2015a). The MILP-relaxation approach. In Koch et al., https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Geißler, B., Martin, A., Morsi, A., & Schewe, L. (2015a). The MILP-relaxation approach. In Koch et al., https://epubs.siam.org/doi/book/10.1137/1.9781611973693 · Zbl 1343.90009
[12] Geißler, B.; Morsi, A.; Schewe, L., A new algorithm for MINLP applied to gas transport energy cost minimization, (Jünger, M.; Reinelt, G., Facets of combinatorial optimization, (2013), Springer, Heidelberg), 321-353 · Zbl 1317.90209
[13] Geißler, B.; Morsi, A.; Schewe, L.; Schmidt, M., Solving power-constrained gas transportation problems using an MIP-based alternating direction method, Computers & Chemical Engineering, 82, (2015)
[14] Geißler, B.; Morsi, A.; Schewe, L.; Schmidt, M., Penalty alternating direction methods for mixed-integer optimization: A new view on feasibility pumps, SIAM Journal on Optimization, 27, 3, 1611-1636, (2017) · Zbl 1371.65051
[15] Geißler, B.; Morsi, A.; Schewe, L., Solving highly detailed gas transport MINLPs: block separability and penalty alternating direction methods, INFORMS Journal on Computing, (2017)
[16] Geißler, B., Towards globally optimal solutions for MINLPs by discretization techniques with applications in gas network optimization, (2011), Friedrich-Alexander-Universität Erlangen-Nürnberg., Ph.D. thesis
[17] Geißler, B.; Kolb, O.; Lang, J.; Leugering, G.; Martin, A.; Morsi, A., Mixed integer linear models for the optimization of dynamical transport networks, Mathematical Methods of Operations Research, 73, 3, 339-362, (2011) · Zbl 1245.90070
[18] Geißler, B., Martin, A., & Morsi, A. Lamatto++. http://www.mso.math.fau.de/edom/projects/lamatto.html; Geißler, B., Martin, A., & Morsi, A. Lamatto++. http://www.mso.math.fau.de/edom/projects/lamatto.html
[19] Geißler, N., Gotzes, U., Hiller, B., Rövekamp, J., & Koch, T. (2015). Regulatory rules for gas markets in Germany and Europe. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Geißler, N., Gotzes, U., Hiller, B., Rövekamp, J., & Koch, T. (2015). Regulatory rules for gas markets in Germany and Europe. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693
[20] Gollmer, R., Schultz, R., & Stangl, C. (2015). The reduced NLP heuristic. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Gollmer, R., Schultz, R., & Stangl, C. (2015). The reduced NLP heuristic. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693 · Zbl 1343.90010
[21] Gotzes, C.; Heitsch, H.; Henrion, R.; Schultz, R., On the quantification of nomination feasibility in stationary gas networks with random load, Mathematical Methods of Operations Research, 84, 2, 427-457, (2016) · Zbl 1354.90031
[22] Gurobi. http://www.gurobi.com; Gurobi. http://www.gurobi.com
[23] Hayn, C., Computing maximal entry and exit capacities of transportation networks, (2016), Friedrich-Alexander-Universität Erlangen-Nürnberg., Ph.D. thesis
[24] Heitsch, H.; Henrion, R.; Leövey, H.; Mirkov, R.; Möller, A.; Römisch, W.; Wegner-Specht, I., Empirical observations and statistical analysis of gas demand data, (2015), In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693
[25] Hennig, K.; Schwarz, R., Using bilevel optimization to find severe transport situations in gas transmission networks, ZIB-Report 16-68, (2016), Zuse Institute Berlin
[26] Hiller, B.; Humpola, J.; Lehmann, T.; Lenz, R.; Morsi, A.; Pfetsch, M. E., Computational results, (2015)
[27] Hiller, B.; Saitenmacher, R.; Walther, T., Polyhedral 3D models for compressors in gas networks. in Koch et al. (2015), ZIB-Report 17-66, (2017), Zuse Institute Berlin
[28] van der Hoeven, T., Math in Gas and the art of linearization, (2004), Rijksuniversiteit Groningen., Ph.D. thesis
[29] Humpola, J., Gas Network Optimization by MINLP, (2014), Technische Universität Berlin., Ph.D. thesis
[30] Humpola, J.; Fügenschuh, A.; Hiller, B.; Koch, T.; Lehmann, T.; Lenz, R., The specialized MINLP approach, (2015), In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693 · Zbl 1343.90013
[31] IBM CPLEX Optimizer. http://www.cplex.com; IBM CPLEX Optimizer. http://www.cplex.com
[32] Joormann, I.; Orlin, J. B.; Pfetsch, M. E., A characterization of irreducible infeasible subsystems in flow networks, Networks, 68, 2, 121-129, (2016) · Zbl 1390.90110
[33] Joormann, I., Schmidt, M., Steinbach, M. C., & Willert, B. M. (2015). What does “feasible” mean? In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Joormann, I., Schmidt, M., Steinbach, M. C., & Willert, B. M. (2015). What does “feasible” mean? In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693
[34] (Koch, T.; Hiller, B.; Pfetsch, M.; Schewe, L., Evaluating gas network capacities, MOS-SIAM Series on Optimization, (2015), SIAM) · Zbl 1322.90007
[35] Misener, R.; Floudas, C. A., Advances for the pooling problem: modeling, global optimization, and computational studies, Applied and Computational Mathematics, 8, 3-22, (2009) · Zbl 1188.90287
[36] Morsi, A., Solving MINLPs on loosely-coupled networks with applications in water and gas network optimization, (2013), Friedrich-Alexander-Universität Erlangen-Nürnberg., Ph.D. thesis
[37] Pfetsch, M. E.; Fügenschuh, A.; Geißler, B.; Geißler, N.; Gollmer, R.; Hiller, B., Validation of nominations in gas network optimization: models, methods, and solutions, Optimization Methods and Software, (2014)
[38] Rose, D.; Schmidt, M.; Steinbach, M. C.; Willert, B. M., Computational optimization of gas compressor stations: MINLP models versus continuous reformulations, Mathematical Methods of Operations Research, 83, 3, 409-444, (2016) · Zbl 1354.90008
[39] Schewe, L., Koch, T., Martin, A., & Pfetsch, M. E. (2015). Mathematical optimization for evaluating gas network capacities. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Schewe, L., Koch, T., Martin, A., & Pfetsch, M. E. (2015). Mathematical optimization for evaluating gas network capacities. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693 · Zbl 1343.90014
[40] Schmidt, M., A generic interior-point framework for nonsmooth and complementarity constrained nonlinear optimization, (2013), Gottfried Wilhelm Leibniz Universität Hannover., Ph.D. thesis
[41] Schmidt, M., An interior-point method for nonlinear optimization problems with locatable and separable nonsmoothness, EURO Journal on Computer Optimization, 3, 4, 309-348, (2015) · Zbl 1329.90144
[42] Schmidt, M.; Steinbach, M. C.; Willert, B. M., A primal heuristic for nonsmooth mixed integer nonlinear optimization, (Jünger, M.; Reinelt, G., Facets of combinatorial optimization, (2013), Springer Berlin Heidelberg), 295-320 · Zbl 1317.90212
[43] Schmidt, M.; Steinbach, M. C.; Willert, B. M., High detail stationary optimization models for gas networks, Optimization and Engineering, 16, 1, 131-164, (2015) · Zbl 1364.90066
[44] Schmidt, M., Steinbach, M. C., & Willert, B. M. (2015b). An MPEC based heuristic. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Schmidt, M., Steinbach, M. C., & Willert, B. M. (2015b). An MPEC based heuristic. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693 · Zbl 1343.90015
[45] Schmidt, M., Steinbach, M. C., & Willert, B. M. (2015c). The precise NLP model. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693; Schmidt, M., Steinbach, M. C., & Willert, B. M. (2015c). The precise NLP model. In Koch et al. (2015), https://epubs.siam.org/doi/book/10.1137/1.9781611973693 · Zbl 1343.90016
[46] Schmidt, M.; Steinbach, M. C.; Willert, B. M., High detail stationary optimization models for gas networks: validation and results, Optimization and Engineering, 17, 2, 437-472, (2016) · Zbl 1364.90067
[47] Schweiger, J., Exploiting structure in nonconvex quadratic optimization and gas network planning under uncertainty, (2017), Technische Universität Berlin., Ph.D. thesis
[48] Schweiger, J.; Liers, F., A decomposition approach for optimum gas network extension with a finite set of demand scenarios, Optimization and Engineering, (2018) · Zbl 1397.90085
[49] Steringa, J. J.; Hoogwerf, M.; Dijkhuis, H.; AL, E., A systematic approach to transmission stress tests in entry-exit systems, PSIG annual meeting, (2015), Pipeline Simulation Interest Group
[50] Vigerske, S.; Gleixner, A., SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, ZIB-Report 16-24, (2016), Zuse Institute Berlin · Zbl 1398.90112
[51] Wächter, A.; Biegler, L. T., On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57, (2006) · Zbl 1134.90542
[52] Willert, B. M., Validation of nominations in gas networks and properties of technical capacities, (2014), Gottfried Wilhelm Leibniz Universität Hannover., Ph.D. thesis
[53] Yoo, A. B.; Jette, M. A.; Grondona, M., SLURM: simple Linux utility for resource management, (Feitelson, D.; Rudolph, L.; Schwiegelshohn, U., Proceedings of the job scheduling strategies for parallel processing: Ninth international workshop, (2003)), 44-60
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.