IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v95y2022i3d10.1007_s00186-021-00752-y.html
   My bibliography  Save this article

A bilevel optimization approach to decide the feasibility of bookings in the European gas market

Author

Listed:
  • Fränk Plein

    (Université Libre de Bruxelles
    Parc scientifique de la Haute Borne)

  • Johannes Thürauf

    (Friedrich-Alexander-Universität Erlangen-Nürnberg
    Energie Campus Nürnberg)

  • Martine Labbé

    (Université Libre de Bruxelles
    Parc scientifique de la Haute Borne)

  • Martin Schmidt

    (Trier University)

Abstract

The European gas market is organized as a so-called entry-exit system with the main goal to decouple transport and trading. To this end, gas traders and the transmission system operator (TSO) sign so-called booking contracts that grant capacity rights to traders to inject or withdraw gas at certain nodes up to this capacity. On a day-ahead basis, traders then nominate the actual amount of gas within the previously booked capacities. By signing a booking contract, the TSO guarantees that all nominations within the booking bounds can be transported through the network. This results in a highly challenging mathematical problem. Using potential-based flows to model stationary gas physics, feasible bookings on passive networks, i.e., networks without controllable elements, have been characterized in the recent literature. In this paper, we consider networks with linearly modeled active elements such as compressors or control valves. Since these active elements allow the TSO to control the gas flow, the single-level approaches for passive networks from the literature are no longer applicable. We thus present a bilevel model to decide the feasibility of bookings in networks with active elements. While this model is well-defined for general active networks, we focus on the class of networks for which active elements do not lie on cycles. This assumption allows us to reformulate the original bilevel model such that the lower-level problem is linear for every given upper-level decision. Consequently, we derive several single-level reformulations for this case. Besides the classic Karush–Kuhn–Tucker reformulation, we obtain three problem-specific optimal-value-function reformulations. The latter also lead to novel characterizations of feasible bookings in networks with active elements that do not lie on cycles. We compare the performance of our methods by a case study based on data from the GasLib.

Suggested Citation

  • Fränk Plein & Johannes Thürauf & Martine Labbé & Martin Schmidt, 2022. "A bilevel optimization approach to decide the feasibility of bookings in the European gas market," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 95(3), pages 409-449, June.
  • Handle: RePEc:spr:mathme:v:95:y:2022:i:3:d:10.1007_s00186-021-00752-y
    DOI: 10.1007/s00186-021-00752-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00186-021-00752-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s00186-021-00752-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Smith, J. Cole & Song, Yongjia, 2020. "A survey of network interdiction models and algorithms," European Journal of Operational Research, Elsevier, vol. 283(3), pages 797-811.
    2. Martin Robinius & Lars Schewe & Martin Schmidt & Detlef Stolten & Johannes Thürauf & Lara Welder, 2019. "Robust optimal discrete arc sizing for tree-shaped potential networks," Computational Optimization and Applications, Springer, vol. 73(3), pages 791-819, July.
    3. Sonja Wogrin & Salvador Pineda & Diego A. Tejada-Arango, 2020. "Applications of Bilevel Optimization in Energy and Electricity Markets," Springer Optimization and Its Applications, in: Stephan Dempe & Alain Zemkoho (ed.), Bilevel Optimization, chapter 0, pages 139-168, Springer.
    4. Lars Schewe & Martin Schmidt & Johannes Thürauf, 2020. "Computing technical capacities in the European entry-exit gas market is NP-hard," Annals of Operations Research, Springer, vol. 295(1), pages 337-362, December.
    5. M. Collins & L. Cooper & R. Helgason & J. Kennington & L. LeBlanc, 1978. "Solving the Pipe Network Analysis Problem Using Optimization Techniques," Management Science, INFORMS, vol. 24(7), pages 747-760, March.
    6. Thomas Kleinert & Martine Labbé & Fr¨ank Plein & Martin Schmidt, 2020. "Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization," Operations Research, INFORMS, vol. 68(6), pages 1716-1721, November.
    7. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    8. Yanıkoğlu, İhsan & Gorissen, Bram L. & den Hertog, Dick, 2019. "A survey of adjustable robust optimization," European Journal of Operational Research, Elsevier, vol. 277(3), pages 799-813.
    9. Ruth Misener & Christodoulos Floudas, 2014. "ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations," Journal of Global Optimization, Springer, vol. 59(2), pages 503-526, July.
    10. Roger Ríos-Mercado & Suming Wu & L. Scott & E. Boyd, 2002. "A Reduction Technique for Natural Gas Transmission Network Optimization Problems," Annals of Operations Research, Springer, vol. 117(1), pages 217-234, November.
    11. James T. Moore & Jonathan F. Bard, 1990. "The Mixed Integer Linear Bilevel Programming Problem," Operations Research, INFORMS, vol. 38(5), pages 911-921, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lars Schewe & Martin Schmidt & Johannes Thürauf, 2022. "Global optimization for the multilevel European gas market system with nonlinear flow models on trees," Journal of Global Optimization, Springer, vol. 82(3), pages 627-653, March.
    2. Holger Heitsch & René Henrion & Thomas Kleinert & Martin Schmidt, 2022. "On convex lower-level black-box constraints in bilevel optimization with an application to gas market models with chance constraints," Journal of Global Optimization, Springer, vol. 84(3), pages 651-685, November.
    3. Johannes Thürauf, 2022. "Deciding the feasibility of a booking in the European gas market is coNP-hard," Annals of Operations Research, Springer, vol. 318(1), pages 591-618, November.
    4. Böttger, T. & Grimm, V. & Kleinert, T. & Schmidt, M., 2022. "The cost of decoupling trade and transport in the European entry-exit gas market with linear physics modeling," European Journal of Operational Research, Elsevier, vol. 297(3), pages 1095-1111.
    5. Lars Schewe & Martin Schmidt & Johannes Thürauf, 2020. "Computing technical capacities in the European entry-exit gas market is NP-hard," Annals of Operations Research, Springer, vol. 295(1), pages 337-362, December.
    6. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    7. Karabulut, Ezgi & Aras, Necati & Kuban Altınel, İ., 2017. "Optimal sensor deployment to increase the security of the maximal breach path in border surveillance," European Journal of Operational Research, Elsevier, vol. 259(1), pages 19-36.
    8. George Kozanidis & Eftychia Kostarelou, 2023. "An Exact Solution Algorithm for Integer Bilevel Programming with Application in Energy Market Optimization," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 573-607, May.
    9. Leonardo Lozano & J. Cole Smith, 2017. "A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem," Operations Research, INFORMS, vol. 65(3), pages 768-786, June.
    10. Ralf Lenz & Kai Helge Becker, 2022. "Optimization of capacity expansion in potential-driven networks including multiple looping: a comparison of modelling approaches," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(1), pages 179-224, March.
    11. Richard Oberdieck & Nikolaos A. Diangelakis & Styliani Avraamidou & Efstratios N. Pistikopoulos, 2017. "On unbounded and binary parameters in multi-parametric programming: applications to mixed-integer bilevel optimization and duality theory," Journal of Global Optimization, Springer, vol. 69(3), pages 587-606, November.
    12. Claudio Contardo & Jorge A. Sefair, 2022. "A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 890-908, March.
    13. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2017. "A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs," Operations Research, INFORMS, vol. 65(6), pages 1615-1637, December.
    14. Fischetti, Matteo & Monaci, Michele & Sinnl, Markus, 2018. "A dynamic reformulation heuristic for Generalized Interdiction Problems," European Journal of Operational Research, Elsevier, vol. 267(1), pages 40-51.
    15. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2021. "The impact of congestion on protection decisions in supply networks under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    16. Dajun Yue & Jiyao Gao & Bo Zeng & Fengqi You, 2019. "A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs," Journal of Global Optimization, Springer, vol. 73(1), pages 27-57, January.
    17. Matthias Köppe & Christopher Thomas Ryan & Maurice Queyranne, 2011. "Rational Generating Functions and Integer Programming Games," Operations Research, INFORMS, vol. 59(6), pages 1445-1460, December.
    18. Fakhry, Ramy & Hassini, Elkafi & Ezzeldin, Mohamed & El-Dakhakhni, Wael, 2022. "Tri-level mixed-binary linear programming: Solution approaches and application in defending critical infrastructure," European Journal of Operational Research, Elsevier, vol. 298(3), pages 1114-1131.
    19. Cambier, Adrien & Chardy, Matthieu & Figueiredo, Rosa & Ouorou, Adam & Poss, Michael, 2022. "Optimizing subscriber migrations for a telecommunication operator in uncertain context," European Journal of Operational Research, Elsevier, vol. 298(1), pages 308-321.
    20. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:mathme:v:95:y:2022:i:3:d:10.1007_s00186-021-00752-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.