1. Deciding feasibility of a booking in the European gas market on a cycle is in P for the case of passive networks
- Author
-
Johannes Thürauf, Fränk Plein, Martine Labbé, Martin Schmidt, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Trier University, Friedrich-Alexander Universität Erlangen-Nürnberg (FAU), and Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique - FNRS under Grant no PDR T0098.18. Fränk Plein thanks the Fonds de la Recherche Scientifique - FNRS for his Aspirant fellowship supporting the research for this publication. He also thanks the Deutsche Forschungsgemeinschaft for their support within the project Z01 in CRC TRR 154. This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government. The third and fourth author also thank the DFG for their support within projects A05, B07, and B08 in CRC TRR 154. Finally, we want to thank Lars Schewe for many fruitful discussions on the topic of this paper.
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Gas networks ,Mathematical optimization ,Computational complexity theory ,Computer Networks and Communications ,Computer science ,Dimension (graph theory) ,0211 other engineering and technologies ,System of polynomial equations ,Modèles mathématiques d'aide à la décision ,02 engineering and technology ,Cycle ,Optimisation de réseaux ,Informatique mathématique ,0502 economics and business ,Real algebraic geometry ,Time complexity ,European entry-exit market ,050210 logistics & transportation ,computational complexity ,021103 operations research ,cycle ,05 social sciences ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,Maximization ,potential-based flows ,Potential-based flows ,Computational complexity ,Nonlinear system ,Bookings ,Flow (mathematics) ,bookings ,Hardware and Architecture ,90B10, 90C30, 90C35, 90C90 ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,gas networks ,Software ,Information Systems - 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., SCOPUS: ar.j, info:eu-repo/semantics/published
- Published
- 2021
- Full Text
- View/download PDF