Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard

Submission Status:under review
  • We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this existing characterization of the literature to prove that FB is coNP-hard by reducing Partition to the infeasibility of a booking. We further prove that computing a potential-difference maximizing load flow scenario is NP-hard even if we can determine the flow direction a priori. From the literature, it is known that FB can be decided in polynomial time on trees and a single cycle. Thus, our hardness result draws the first line that separates the easy from the hard variants of FB and finally answers that FB is hard in general.
Metadaten
Author:Johannes Thürauf
Document Type:Preprint
Language:English
Date of Publication (online):2020/05/20
Date of first Publication:2020/05/20
Release Date:2020/05/20
Tag:Potential-based flows, Gas networks, Computational complexity, European entry-exit market, Bookings
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Subprojects:B07
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International