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

Submission Status:Published
  • 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.

Download full text files

Export metadata

Metadaten
Author:Martine Labbé, Fränk Plein, Martin Schmidt, Johannes Thürauf
DOI:https://doi.org/10.1007/s00186-021-00752-y
Parent Title (German):Networks
Document Type:Article
Language:English
Date of Publication (online):2019/11/12
Date of first Publication:2019/11/12
Release Date:2019/11/12
Tag:Bookings; Computational complexity; European entry-exit market; Gas networks; Potential-based flows
Volume:78
Issue:2
Page Number:25
First Page:128
Last Page:152
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Universität Trier
Université libre de Bruxelles
Subprojects:A05
B07
Z01
B08
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International