Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks

Labbé M, Plein F, Schmidt M, Thürauf J (2021)

Publication Language: English

Publication Status: Accepted

Publication Type: Journal article, Original article

Future Publication Type: Journal article

Publication year: 2021

Journal

Networks Wiley-Blackwell

DOI: 10.1002/net.22003

Abstract

We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e., do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential-based flows. This enables us to solve the decision variant of the nonlinear potential-difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial-time algorithm. The characterization in terms of potential-difference maximizing load flow scenarios then leads to a polynomial-time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single-cycle networks.

Authors with CRIS profile

Johannes Thürauf Economics - Discrete Optimization - Mathematics (EDOM)

Related research project(s)

MIP techniques for equilibrium models with integer constraints (B07) (2018 - 2022) TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154) July 1, 2018 - June 30, 2022 Decomposition methods for mixed-integer optimal control (A05) (2018 - 2022) TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154) July 1, 2018 - June 30, 2022 Multilevel mixed-integer nonlinear optimization for gas markets (B08) (2018 - 2022) TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154) July 1, 2018 - June 30, 2022 Energiemarktdesign (EMD) Energie Campus Nürnberg (EnCN2) Jan. 1, 2017 - Dec. 31, 2021

Involved external institutions

Universität Trier DE Germany (DE)

How to cite

APA:

Labbé, M., Plein, F., Schmidt, M., & Thürauf, J. (2021). Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks. Networks. https://doi.org/10.1002/net.22003

MLA:

Labbé, Martine, et al. "Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks." Networks (2021).

BibTeX: Download