Abstract
As a consequence of the liberalisation of the European gas market in the last decades, gas trading and transport have been decoupled. At the core of this decoupling are so-called bookings and nominations. Bookings are special capacity right contracts that guarantee that a specified amount of gas can be supplied or withdrawn at certain entry or exit nodes of the network. These supplies and withdrawals are nominated at the day-ahead. The special property of bookings then is that they need to be feasible, i.e., every nomination that complies with the given bookings can be transported. While checking the feasibility of a nomination can typically be done by solving a mixed-integer nonlinear feasibility problem, the verification of feasibility of a set of bookings is much harder. The reason is the robust nature of feasibility of bookings—namely that for a set of bookings to be feasible, all compliant nominations, i.e., infinitely many, need to be checked for feasibility. In this paper, we consider the question of how to verify the feasibility of given bookings for a number of special cases. For our physics model we impose a steady-state potential-based flow model and disregard controllable network elements. For this case we derive a characterisation of feasible bookings, which is then used to show that the problem is in coNP for the general case but can be solved in polynomial time for linear potential-based flow models. Moreover, we present a dynamic programming approach for deciding the feasibility of a booking in tree-shaped networks even for nonlinear flow models. It turns out that the hardness of the problem mainly depends on the combination of the chosen physics model as well as the specific network structure under consideration. Thus, we give an overview over all settings for which the hardness of the problem is known and finally present a list of open problems.
Similar content being viewed by others
References
Aßmann D, Liers F, Stingl M (2019) Decomposable robust two-stage optimization: an application to gas network operations under uncertainty. Networks. https://doi.org/10.1002/net.21871
Bakhouya B, De Wolf D (2007) The gas transmission problem when the merchant and the transport functions are disconnected. Technical Report, Ieseg, Universite catholique de Lille, Jan. https://www.researchgate.net/publication/253816284_The_gas_transmission_problem_when_the_merchant_and_the_transport_functions_are_disconnected. Accessed 8 Nov 2017
Baumrucker BT, Biegler LT (2010) MPEC strategies for cost optimization of pipeline operations. Comput Chem Eng 34(6):900–913. https://doi.org/10.1016/j.compchemeng.2009.07.012
Bermúdez A, González-Díaz J, González-Diéguez FJ, González-Rueda ÁM, de Córdoba MP (2014) Simulation and optimization models of steady-state gas transmission networks. In: Energy procedia. 3rd Trondheim gas technology conference, 4–5 June, vol 64 (Supplement C 2015), pp 130–139. https://doi.org/10.1016/j.egypro.2015.01.016
Birkhoff G, Diaz JB (1956) Non-linear network problems. Q Appl Math 13(4):431–443
Dantzig GB (1957) Discrete-variable extremum problems. Oper Res 5(2):266–288. https://doi.org/10.1287/opre.5.2.266
De Wolf D, Smeers Y (2000) The gas transmission problem solved by an extension of the simplex algorithm. Manag Sci 46(11):1454–1465. https://doi.org/10.1287/mnsc.46.11.1454.12087
Directive 2003/55/EC of the European Parliament and of the Council of 26 June 2003 concerning common rules for the internal market in natural gas and repealing Directive 98/30/EC (OJ L 176, pp 57–78)
Directive 2009/73/EC of the European Parliament and of the Council concerning common rules for the internal market in natural gas and repealing Directive 2003/55/EC (OJ L 211 pp 36–54)
Directive 98/30/EC of the European Parliament and of the Council of 22 June 1998 concerning common rules for the internal market in natural gas (OJ L 204 pp 1–12)
Domschke P, Geißler B, Kolb O, Lang J, Martin A, Morsi A (2011) Combination of nonlinear and linear optimization of transient gas networks. INFORMS J Comput 23(4):605–617. https://doi.org/10.1287/ijoc.1100.0429
Fügenschuh A, Geißler B, Gollmer R, Hayn C, Henrion R, Hiller B, Humpola J, Koch T, Lehmann T, Martin A, Mirkov R, Morsi A, Rövekamp J, Schewe L, Schmidt M, Schultz R, Schwarz R, Schweiger J, Stangl C, Steinbach MC, Willert BM (2014a) Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets. Energy Syst 5(3):449–473. https://doi.org/10.1007/s12667-013-0099-8
Fügenschuh A, Junosza-Szaniawski K, Kwasiborski S (2014b) The reservation-allocation network flow problem. Technical Report. https://www.researchgate.net/publication/265126185_The_Reservation-Allocation_Network_Flow_Problem. Accessed 26 June 2018
Fügenschuh A, Geißler B, Gollmer R, Morsi A, Rövekamp J, Schmidt M, Spreckelsen K, Steinbach MC (2015) Chapter 2: physical and technical fundamentals of gas networks. In: Koch T, Hiller B, Pfetsch ME, Schewe L (eds) Evaluating gas network capacities. Society for Industrial and Applied Mathematics, Philadelphia, pp 17–43. https://doi.org/10.1137/1.9781611973693.ch2
Geißler B (2011) Towards globally optimal solutions for MINLPs by discretization techniques with applications in gas network optimization. Ph.D. thesis, Friedrich-Alexander Universität Erlangen-Nürnberg, Germany
Geißler B, Morsi A, Schewe L (2013) A new algorithm for MINLP applied to gas transport energy cost minimization. In: Junger M, Reinelt G (eds) Facets of combinatorial optimization. Springer, Berlin, pp 321–353. https://doi.org/10.1007/978-3-642-38189-8_14
Geißler B, Martin A, Morsi A, Schewe L (2015a) The MILP-relaxation approach. In: Koch T, Hiller B, Pfetsch ME, Schewe L (eds) Evaluating gasnetwork capacities. Society for Industrial and Applied Mathematics, Philadelphia, pp 103–122. https://doi.org/10.1137/1.9781611973693.ch6
Geißler B, Morsi A, Schewe L, Schmidt M (2015b) Solving power-constrained gas transportation problems using an MIP-based alternating direction method. Comput Chem Eng 82:303–317. https://doi.org/10.1016/j.compcriemeng.2015.07.005
Geißler B, Morsi A, Schewe L, Schmidt M (2018) Solving highly detailed gas transport MINLPs: block separability and penalty alternating direction methods. INFORMS J Comput 30(2):309–323. https://doi.org/10.1287/ijoc.2017.0780
Gotzes C, Heitsch H, Henrion R, Schultz R (2016) On the quantification of nomination feasibility in stationary gas networks with random load. Math Methods Oper Res 84(2):427–457. https://doi.org/10.1007/s00186-016-0564-y
Grimm V, Schewe L, Schmidt M, Zöttl G (2019) A multilevel model of the European entry-exit gas market. Math Methods Oper Res 89(2):223–255. https://doi.org/10.1007/s00186-018-0647-z
Groß M, Pfetsch ME, Schewe L, Schmidt M, Skutella M (2019) Algorithmic results for potential-based flows: easy and hard cases. Networks 73(3):306–324. https://doi.org/10.1002/net.21865
Hante FM, Leugering G, Martin A, Schewe L, Schmidt M (2017) Challenges in optimal control problems for gas and fluid flow in networks of pipes and canals: from modeling to industrial applications. In: Manchanda P, Lozi R, Siddiqi AH (eds) Industrial mathematics and complex systems: emerging mathematical models, methods and algorithms. Industrial and applied mathematics. Springer Singapore, Singapore, pp 77–122. https://doi.org/10.1007/978-981-10-3758-0_5
Hayn C (2017) Computing maximal entry and exit capacities of transportation networks-complexity analysis and a discrete relaxation applied to gas transmission systems. Verlag Dr. Hut, Munich
Hewicker C, Kesting S (2009) The new entry-exit model in the EU and its consequences for gas supply companies. In: Bausch A, Schwenker B (eds) Handbook utility management. Springer, Berlin, pp 477–491. https://doi.org/10.1007/978-3-540-79349-6_28
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin. https://doi.org/10.1007/978-3-540-24777-7
Kirchhoff G (1847) Ueber Die Auflosung Der Gleichungen, Auf Welche Man Bei Der Untersuchung Der Linearen Vertheilung Galvanischer Ströme Geführt Wird. Ann Phys 148(12):497–508
Kirschen D, Strbac G (2005) Transmission networks and electricity markets. Fundam Power Syst Econ 2005:141–204. https://doi.org/10.1002/0470020598.ch6
Koch T, Hiller B, Pfetsch ME, Schewe L (2015) Evaluating gas network capacities. SIAM, Philadelphia. https://doi.org/10.1137/1.9781611973693
Larock BE, Jeppson RW, Watters GZ, Jeppson RW, Watters GZ (1999) Hydraulics of pipeline systems. CRC Press, Boca Raton. https://doi.org/10.1201/9781420050318
Martin A, Möller M, Moritz S (2006) Mixed integer models for the stationary case of gas network optimization. Math Program 105(2):563–582. https://doi.org/10.1007/s10107-005-0665-5
Martin A, Geißler B, Hayn C, Morsi A, Schewe L, Hiller B, Humpola J, Koch T, Lehmann T, Schwarz R, Schweiger J, Pfetsch M, Schmidt M, Steinbach M, Willert B, Schultz R (2011) Optimierung Technischer Kapazitäten in Gasnetzen. In: Optimierung in der Energiewirtschaft. VDI-Berichte 2157, pp 105–114. https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1512
Maugis JJ (1977) Étude de réseaux de transport et de distribution de fluide. RAIRO Oper Res 11(2):243–248. https://doi.org/10.1051/ro/1977110202431
Ríos-Mercado RZ, Borraz-Sánchez C (2015) Optimization problems in natural gas transportation systems: a state-of-the-art review. Appl Energy 147(Supplement C):536–555. https://doi.org/10.1016/j.apenergy.2015.03.017
Ríos-Mercado RZ, Suming W, Scott LR, Boyd EA (2000) Preprocessing on natural gas transmission networks. Technical Report. http://pisis.fime.uanl.mx/ftp/pubs/reports/2000/pisis-2000-01.pdf. Accessed 1 Feb 2018
Ríos-Mercado RZ, Wu S, Scott LR, Boyd EA (2002) A reduction technique for natural gas transmission network optimization problems. Ann Oper Res 117(1–4):217–234. https://doi.org/10.1023/A:1021529709006
Robinius M, Schewe L, Schmidt M, Stolten D, Thürauf J, Welder L (2019) Robust optimal discrete arc sizing for tree-shaped potential networks. Comput Optim Appl 73(3):791–819. https://doi.org/10.1007/s10589-019-00085-x
Rose D, Schmidt M, Steinbach MC, Willert BM (2016) Computational optimization of gas compressor stations: MINLP models versus continuous reformulations. Math Methods Oper Res 83(3):409–444. https://doi.org/10.1007/s00186-016-0533-5
Schewe L, Schmidt M (2019) The impact of potential-based physics models on pricing in energy networks. Central Eur J Oper Res. https://doi.org/10.1007/s10100-019-00616-1
Schewe L, Schmidt M, Thürauf J (2018) Structural properties of feasible bookings in the European entry-exit gas market system. Technical report. http://www.optimization-online.org/DB_HTML/2018/09/6831.html. Accessed 24 Oct 2018
Schmidt M (2013) A generic interior-point framework for nonsmooth and complementarity constrained nonlinear optimization. Ph.D. thesis, Leibniz Universitat Hannover
Schmidt M, Steinbach MC, Willert BM (2013) A primal heuristic for nonsmooth mixed integer nonlinear optimization. In: Junger M, Reinelt G (eds) Facets of combinatorial optimization. Springer, Berlin, pp 295–320. https://doi.org/10.1007/978-3-642-38189-8_13
Schmidt M, Steinbach MC, Willert BM (2015a) An MPEC based heuristic. In: Koch T, Hiller B, Pfetsch ME, Schewe L (eds) Evaluating gas network capacities. SIAM-MOS series on optimization, Chap 9. SIAM, Philadelphia, pp 163–180. https://doi.org/10.1137/1.9781611973693.ch9
Schmidt M, Steinbach MC, Willert BM (2015b) Chapter 10: the precise NLP model. In: Koch T, Hiller B, Pfetsch ME, Schewe L (eds) Evaluating gas network capacities. Society for Industrial and Applied Mathematics, Philadelphia, pp 181–210. https://doi.org/10.1137/1.9781611973693.ch10
Schmidt M, Steinbach MC, Willert BM (2015c) High detail stationary optimization models for gas networks. Optim Eng 16(1):131–164. https://doi.org/10.1007/s11081-014-9246-x
Schmidt M, Steinbach MC, Willert Bernhard M (2016) High detail stationary optimization models for gas networks: validation and results. Optim Eng 17(2):437–472. https://doi.org/10.1007/s11081-015-9300-3
Stangl C (2014) Modelle, Strukturen und Algorithmen für stationäre Flusse in Gasnetzen. Ph.D. thesis, Universität Duisburg-Essen, http://duepublico.uni-duisburg-essen.de/servlets/DocumentServlet?id=35564. Accessed 3 Feb 2018
Willert BM (2014) Validation of nominations in gas networks and properties of technical capacities. Ph.D. thesis, Technische Informationsbibliothek und Universitätsbibliothek Hannover (TIB)
Wong P, Larson R (1968) Optimization of natural-gas pipeline systems via dynamic programming. IEEE Trans Autom Control 13(5):475–481. https://doi.org/10.1109/TAC.1968.1098990
Acknowledgements
Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique - FNRS under Grant No. PDR T0098.18. Fränk Plein thanks the Fonds de la Recherche Scientifique - FNRS for his Aspirant fellowship supporting the research for this publication. He also thanks the Deutsche Forschungsgemeinschaft for their support within the Project Z01 in the “Sonderforschungsbereich / Transregio 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks”. Martin Schmidt thanks the Deutsche Forschungsgemeinschaft for their support within projects A05 and B08 in the “Sonderforschungsbereich/Transregio 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks”. This research has been performed as part of the Energie Campus Nürnberg (EnCN) and is supported by funding of the Bavarian State Government. Finally, we want to thank Johannes Thürauf for carefully reading a former version of this manuscript and for his comments that helped to improve the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Labbé, M., Plein, F. & Schmidt, M. Bookings in the European gas market: characterisation of feasibility and computational complexity results. Optim Eng 21, 305–334 (2020). https://doi.org/10.1007/s11081-019-09447-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11081-019-09447-0