A gas network has a number of entry and exit points. Shippers independently contract the right to use the network on these points. Only at the time of actual use, the combination of entries and exits is known. One of the questions is, if all possible future transport use by the shippers can be met.
Past. In the past the situation of gas transport was merely static. So it was possible to take a long period (years) to build expert knowledge which severe realizations (these are called shipping variants) should be considered to see if a new contract can be honoured.
Present. Currently a method is used, based on simplified models, to generate a limited set of shipping variants which should be considered when a new situation occurs. Since the changes in law and new energy sources lead to many more different situations such a method should be fast, robust, structured, objective, based on simple principles and generates a small set of shipping variants. The proposed method satisfies most of the requirements and reproduces known shipping variants obtained by expert knowledge.
Future. Although the method works well for the current situation it is important to base the method on a firm mathematical basis. Furthermore it would be nice to reduce the number of shipping variants even more.
Open questions are:
- Which physical quantities, metrics and techniques should be used to find those transport conditions that determine the size of the infrastructure?
- Which techniques are available to sufficiently reduce the obtained set to find an exhaustive subset of which the elements are mutually exclusive, given a required accuracy?
- What mathematical optimisation tools can be used to maximise the load and minimise the number of scenarios, given that all transport paths from entry to exit need to be covered.
Literature:
A Systematic Approach to Transmission Stress Tests in Entry-Exit Systems Jarig J. Steringa, Marco Hoogwerf, Harry Dijkhuis
http://www.oges.info/89799/systematic-approach-transmission-stress-tests-entry-systems
A stochastic approach to allocation of capacity in a gas transmission network D.I. van Huizen
essay.utwente.nl/67166/1/vanhuizen_ma_eemcs.pdf
Comparing severe gas transport situations through the network: Similarity or reduction methods
Kimberley Lindenberg
http://ta.twi.tudelft.nl/nw/users/vuik/numanal/lindenberg_eng.html
Optimization methods:
For the problem a variety of optimization methods have been used: From linear programs to mixed-integer nonlinear programs. The choice of method depends first and foremost on the chosen model for the pressure drop in pipes and whether one uses a time-dependent model or not. Among the easy cases are the following: If the network is topologically simple, say a so-called gun barrel network, then dynamic programming approaches are the state-of-the-art (see the survey of Carter). If one chooses to use a stationary model, then it can be reasonable to use an algebraic solution of a simplified system, a special case of these is known as the so-called Weymouth equation. The problem then is a mixed-integer nonlinear program which can be tackled directly with off-theshelf MINLP solvers for small networks or using specialized methods for larger networks (see e.g. Koch et al. [8]). Popular choices for methods include using piecewise linear approximations/linearizations to obtain MIP models [3, 4, 9],
MPEC-based models (see Baumrucker and Biegler [1], Schmidt et al. [11]). Neglecting the discrete decisions leads to NLP models which can be solved to local optimality (see Schmidt et al. [12]). But also these equations can be simplified even further. One approach is to locally linearize them around a working point, an approach that is very successful in practice (see van der Hoeven [5]). If one opts to use the full Euler equations in the instationary setting one obtains a mixed-integer PDAE-constrained optimal control problem that is intractable for current methods except for very simple networks. Another approach with high physical accuracy is to use a (sub)gradient-based approach on top of an accurate simulation tool (see Jenícek [7] and Vostrý [13]). One approach to simplify the full Euler equations is to only consider the isothermal case. Here using piecewise-linear models leads to MIP models that can be solved for nontrivial networks (see Domschke et al. [2]).
Data: The GasLib http://gaslib.zib.de provides benchmark instances for planning problems in gas pipeline transmission. The files originate from real-world data that was used in a research collaboration with Open Grid Europe GmbH [10]. An explanation of the custom XML formats and further references can be found in a recent preprint [2]. In addition to the network data, fixed MINLP models implemented in GAMS are provided for solver developers.
Software: (by Robert Schwarz)
Lamatto++ http://www.mso.math.fau.de/edom/projects/lamatto.html is a software framework written in C++ that supports the modeling of optimization problems on networks. It was applied in particular to planning problems in gas pipeline transmission, see http://bookstore.siam.org/mo21 and http://www.tandfonline.com/doi/abs/10.1080/10556788.2014.888426
The relevant features include a model abstraction to state-of-the-art MIP solvers as well as GAMS, preprocessing and bounds strenghtening on network models, fully automatic generation of MIP approximation for nonlinear constraints with a given error tolerance, and computing with physical units. Data I/O is done through XML files, where the GasLib provides examples.
The GasLib [1] provides benchmark instances for planning problems in gas pipeline transmission. The files originate from real-world data that was used in a research collaboration with Open Grid Europe GmbH. An explanation for the file formats and further references can be found in a recent preprint [2]. In addition to the network data, MINLP models implemented in GAMS are provided for solver developers.
[2] http://www.optimization-online.org/DB_HTML/2015/11/5216.html
References
[1] B. T. Baumrucker and L. T. Biegler. “MPEC strategies for cost optimization of pipeline operations”. In: Comp. Chem. Eng. 34.6 (2010), pp. 900–913. issn: 0098-1354. doi: 10.1016/j.compchemeng.2009.07.012.
[2] Pia Domschke, Björn Geißler, Oliver Kolb, Jens Lang, Alexander Martin, and Antonio Morsi. “Combination of Nonlinear and Linear Optimization of Transient Gas Networks”. In: INFORMS Journal on Computing 23.4 (2011), pp. 605–617.
[3] Björn Geißler, Alexander Martin, Antonio Morsi, and Lars Schewe. “The MILP-relaxation approach”. In: Evaluating Gas Network Capacities. Ed. by Thorsten Koch, Benjamin Hiller, Marc E. Pfetsch, and Lars Schewe.
SIAM-MOS series on Optimization. SIAM, Mar. 2015. Chap. 7. isbn: 978-1-611973-68-6.
[4] Björn Geißler, Antonio Morsi, Lars Schewe, and Martin Schmidt. “Solving Power-Constrained Gas Transportation Problems using an Alternating Direction Method”. In: Computers & Chemical Engineering 82.2 (2015), pp. 303–317. doi: 10.1016/j.compchemeng.2015.07.005.
[5] Tom van der Hoeven. “Math in Gas and the art of linearization”. PhD thesis. Rijksuniversiteit Groningen, 2004.
[6] Jesco Humpola, Imke Joormann, Djamal Oucherif, Marc E. Pfetsch, Lars Schewe, Martin Schmidt, and Robert Schwarz. GasLib – A Library of Gas Network Instances. Nov. 2015. url: http://www.optimization-online. org/DB_HTML/2015/11/5216.html.
[7] Tomáš Jenícek. “Steady-State Optimization of Gas Transport”. In: Proceedings of 2nd International Workshop SIMONE on Innovative Approaches to Modeling and Optimal Control of Large Scale Pipeline Networks.
Prague, 1993, pp. 26–38.
[8] Thorsten Koch, Benjamin Hiller, Marc E. Pfetsch, and Lars Schewe, eds. Evaluating Gas Network Capacities. SIAM-MOS series on Optimization. SIAM, Mar. 2015. xvi + 376. isbn: 978-1-611973-68-6.
[9] Alexander Martin, M. Möller, and S. Moritz. “Mixed Integer Models for the Stationary Case of Gas Network Optimization”. In: Mathematical Programming, Series B 105 (2006), pp. 563–582.
[10] Marc E. Pfetsch, Armin Fügenschuh, Björn Geißler, Nina Geißler, Ralf Gollmer, Benjamin Hiller, Jessica Rövekamp, Jesco Humpola, Thorsten Koch, Thomas Lehmann, Alexander Martin, Antonio Morsi, Lars Schewe,Martin Schmidt, Robert Schwarz, Rüdiger Schultz, Jonas Schweiger, Claudia Stangl, Marc C. Steinbach, Stefan Vigerske, and Bernhard M. Willert. “Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions”. In: Optim. Methods Softw. 30.1 (2015), pp.15–53. doi: 10.1080/10556788.2014.888426.
[11] Martin Schmidt, Marc C. Steinbach, and Bernhard M. Willert. “An MPEC based heuristic”. In: ed. by Thorsten Koch, Benjamin Hiller, Marc E. Pfetsch, and Lars Schewe. SIAM-MOS series on Optimization. SIAM,Mar. 2015. Chap. 9, pp. 163–179. isbn: 978-1-611973-68-6. doi: 10.1137/1.9781611973693.ch9.
[12] Martin Schmidt, Marc C. Steinbach, and Bernhard M. Willert. “The precise NLP model”. In: ed. by Thorsten Koch, Benjamin Hiller, Marc E. Pfetsch, and Lars Schewe. SIAM-MOS series on Optimization. SIAM,Mar.2015. Chap. 10, pp. 181–210. isbn: 978-1-611973-68-6. doi: 10.1137/1.9781611973693.ch10.
[13] Zdenek Vostrý. “Transient Optimization of Gas Transport and Distribution”. In: Proceedings of 2nd International Workshop SIMONE on Innovative
Approaches to Modeling and Optimal Control of Large Scale Pipeline Networks. Prague, Sept. 1993, pp. 53–62.
Contributors:
Prof. Kees Vuik, Delft University of Technology
Dr Lars Schewe, Universität Erlangen-Nürnberg