Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks
Preprint
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.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Bookings in the European gas market: characterisation of feasibility and computational complexity resultsOptimization and Engineering, 2019
- Structural properties of feasible bookings in the European entry–exit gas market system4OR, 2019
- Robust optimal discrete arc sizing for tree-shaped potential networksComputational Optimization and Applications, 2019
- Decomposable robust two‐stage optimization: An application to gas network operations under uncertaintyNetworks, 2019
- Algorithmic results for potential‐based flows: Easy and hard casesNetworks, 2018
- On the quantification of nomination feasibility in stationary gas networks with random loadMathematical Methods of Operations Research, 2016
- High detail stationary optimization models for gas networksOptimization and Engineering, 2014
- A New Algorithm for MINLP Applied to Gas Transport Energy Cost Minimization2013
- Mixed Integer Models for the Stationary Case of Gas Network OptimizationMathematical Programming, 2005
- Adjustable robust solutions of uncertain linear programsMathematical Programming, 2004