Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/307500 
Autor:innen: 
Erscheinungsjahr: 
2022
Quellenangabe: 
[Journal:] Annals of Operations Research [ISSN:] 1572-9338 [Volume:] 318 [Issue:] 1 [Publisher:] Springer US [Place:] New York, NY [Year:] 2022 [Pages:] 591-618
Verlag: 
Springer US, New York, NY
Zusammenfassung: 
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.
Schlagwörter: 
Potential-based flows
Gas networks
Computational complexity
European entry-exit market
Bookings
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.