Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

Martine Labbé 1 Fränk Plein 2, 1 Martin Schmidt 3 Johannes Thürauf 4
1 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
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.
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-02360972
Contributor : Fränk Plein <>
Submitted on : Friday, October 16, 2020 - 5:01:44 PM
Last modification on : Friday, November 27, 2020 - 2:20:11 PM

File

preprint-version-2020-10-16.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02360972, version 3

Collections

Citation

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 for the Case of Passive Networks. 2020. ⟨hal-02360972v3⟩

Share

Metrics

Record views

16

Files downloads

109