| Autor: |
Labbé, Martine, Plein, Fränk, Schmidt, Martin, Thürauf, Johannes |
| Předmět: |
|
| Zdroj: |
Networks; Sep2021, Vol. 78 Issue 2, p128-152, 25p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Plný text