Journal
NETWORKS
Volume 78, Issue 2, Pages 128-152Publisher
WILEY
DOI: 10.1002/net.22003
Keywords
bookings; computational complexity; cycle; European entry‐ exit market; gas networks; potential‐ based flows
Funding
- Bayerische Staatsregierung
- Deutsche Forschungsgemeinschaft [TRR 154]
- Fonds De La Recherche Scientifique - FNRS [PDR T0098.18]
Ask authors/readers for more resources
The study demonstrates that the feasibility of bookings in the European entry-exit gas market can be determined in polynomial time on passive single-cycle networks. By solving polynomially many nonlinear potential-based flow models, the decision variant of the potential-difference maximization can be reduced to a system of polynomials of constant dimension for a polynomial-time algorithm.
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
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available