Computing technical capacities in the European entry-exit gas market is NP-hard

  • PDF / 530,599 Bytes
  • 26 Pages / 439.37 x 666.142 pts Page_size
  • 80 Downloads / 137 Views

DOWNLOAD

REPORT


Computing technical capacities in the European entry-exit gas market is NP-hard Lars Schewe1

· Martin Schmidt2

· Johannes Thürauf3,4

© The Author(s) 2020

Abstract As a result of its liberalization, the European gas market is organized as an entry-exit system in order to decouple the trading and transport of natural gas. Roughly summarized, the gas market organization consists of four subsequent stages. First, the transmission system operator (TSO) is obliged to allocate so-called maximal technical capacities for the nodes of the network. Second, the TSO and the gas traders sign mid- to long-term capacity-right contracts, where the capacity is bounded above by the allocated technical capacities. These contracts are called bookings. Third, on a day-ahead basis, gas traders can nominate the amount of gas that they inject or withdraw from the network at entry and exit nodes, where the nominated amount is bounded above by the respective booking. Fourth and finally, the TSO has to operate the network such that the nominated amounts of gas can be transported. By signing the booking contract, the TSO guarantees that all possibly resulting nominations can indeed be transported. Consequently, maximal technical capacities have to satisfy that all nominations that comply with these technical capacities can be transported through the network. This leads to a highly challenging mathematical optimization problem. We consider the specific instantiations of this problem in which we assume capacitated linear as well as potential-based flow models. In this contribution, we formally introduce the problem of Computing Technical Capacities (CTC) and prove that it is NP-complete on trees and NPhard in general. To this end, we first reduce the Subset Sum problem to CTC for the case of capacitated linear flows in trees. Afterward, we extend this result to CTC with potential-based flows and show that this problem is also NP-complete on trees by reducing it to the case of capacitated linear flow. Since the hardness results are obtained for the easiest case, i.e., on tree-shaped networks with capacitated linear as well as potential-based flows, this implies the hardness of CTC for more general graph classes. Keywords European entry-exit gas market · Technical capacities · Potential-based flows · Computational complexity · NP-hardness Mathematics Subject Classification 90B10 · 90C35 · 90C60 · 90C90

B

Martin Schmidt [email protected]

Extended author information available on the last page of the article

123

Annals of Operations Research

1 Introduction The European gas market is organized as a so-called entry-exit market system, which has been the outcome of the European gas market liberalization; see Directive (1998, 2009, 2003). The main goal of the entry-exit system is to decouple the trading and transport of gas. The current market organization that should achieve this goal is mainly split into different stages in which the transmission system operator (TSO) and the gas traders interact with each other. First, the TSO is