  


Computing Technical Capacities in the European EntryExit Gas Market is NPHard
Lars Schewe(lars.scheweed.ac.uk) Abstract: As a result of its liberalization, the European gas market is organized as an entryexit 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 socalled maximal technical capacities for the nodes of the network. Second, the TSO and the gas traders sign mid to longterm capacityright contracts, where the capacity is bounded above by the allocated technical capacities. These contracts are called bookings. Third, on a dayahead 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 potentialbased flow models. In this contribution, we formally introduce the problem of Computing Technical Capacities (CTC) and prove that it is NPcomplete. 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 potentialbased flows and show that this problem is also NPcomplete 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 treeshaped networks with capacitated linear as well as potentialbased flows, this implies the hardness of CTC for more general graph classes. Keywords: European EntryExit Gas Market, Technical Capacities, PotentialBased Flows, Computational Complexity, NPHardness Category 1: Network Optimization Category 2: Applications  Science and Engineering Citation: Download: [PDF] Entry Submitted: 01/21/2020 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  