Optimization Online


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

Johannes Thürauf (johannes.thuerauf***at***fau.de)

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.

Keywords: Potential-based flows, Gas networks, Computational complexity, European entry-exit market, Bookings

Category 1: Network Optimization

Category 2: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 05/20/2020
Entry Accepted: 05/20/2020
Entry Last Modified: 07/06/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society