Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2019

Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P

Résumé

We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on passive single-cycle networks, i.e., on networks without 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.
Fichier principal
Vignette du fichier
preprint-version-2019-11-12.pdf (664.2 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02360972 , version 1 (13-11-2019)
hal-02360972 , version 2 (16-07-2020)
hal-02360972 , version 3 (16-10-2020)

Identifiants

  • HAL Id : hal-02360972 , version 1

Citer

Martine Labbé, Fränk Plein, Martin Schmidt, Johannes Thürauf. Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P. 2019. ⟨hal-02360972v1⟩
75 Consultations
162 Téléchargements

Partager

Gmail Facebook X LinkedIn More