Optimization Online


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

Martine Labbé(martine.labbe***at***ulb.ac.be)
Fränk Plein(frank.plein***at***ulb.ac.be)
Martin Schmidt(martin.schmidt***at***uni-trier.de)
Johannes Thürauf(johannes.thuerauf***at***fau.de)

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. 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.

Keywords: Gas networks, European entry-exit market, Bookings, Potential-based flows, Computational complexity, Cycle

Category 1: Network Optimization

Category 2: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 11/12/2019
Entry Accepted: 11/12/2019
Entry Last Modified: 11/12/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society