Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/307500 
Year of Publication: 
2022
Citation: 
[Journal:] Annals of Operations Research [ISSN:] 1572-9338 [Volume:] 318 [Issue:] 1 [Publisher:] Springer US [Place:] New York, NY [Year:] 2022 [Pages:] 591-618
Publisher: 
Springer US, New York, NY
Abstract: 
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.
Subjects: 
Potential-based flows
Gas networks
Computational complexity
European entry-exit market
Bookings
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.