Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P
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. 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 32 references indexed in Scilit:
- 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
- Challenges in Optimal Control Problems for Gas and Fluid Flow in Networks of Pipes and Canals: From Modeling to Industrial Applications2017
- On the quantification of nomination feasibility in stationary gas networks with random loadMathematical Methods of Operations Research, 2016
- Computational optimization of gas compressor stations: MINLP models versus continuous reformulationsMathematical Methods of Operations Research, 2016
- A New Algorithm for MINLP Applied to Gas Transport Energy Cost Minimization2013
- A Primal Heuristic for Nonsmooth Mixed Integer Nonlinear Optimization2013
- The New Entry-exit Model in the EU and Its Consequences for Gas Supply Companies2008
- Algorithms in Real Algebraic Geometry2006
- Geometric Algorithms and Combinatorial Optimization1993