The 21st of June, 2021, Fränk Plein succesfully defended his thesis titled
When Bilevel Optimization Meets Gas Networks: Feasibility of Bookings in the European Entry-Exit Gas Market: Computational Complexity Results and Bilevel Optimization Approaches.
The jury was composed by:
- Thomas STÜTZLE, Université libre de Bruxelles
- Bernard FORTZ, Université libre de Bruxelles
- Martine LABBÉ, Université libre de Bruxelles
- Martin SCHMIDT, Universität Trier
- Sven DE VRIES, Universität Trier
- Lars SCHEWE, The University of Edinburgh
Thesis abstract: Transport and trade of gas are decoupled after the liberalization of the European gas markets, which are now organized as so-called entry-exit systems. At the core of this market system are bookings and nominations, two special capacity-right contracts that grant traders access to the gas network. The latter is operated by a separate entity, known as the transmission system operator (TSO), who is in charge of the transport of gas from entry to exit nodes. In the mid to long term, traders sign a booking contract with the TSO to obtain injection and withdrawal capacities at entry and exit nodes, respectively. On a day-ahead basis, they then nominate within these booked capacities a balanced load flow of the planned amounts of gas to be injected into and withdrawn from the network the next day. The key property is that by signing a booking contract, the TSO is obliged to guarantee transportability for all balanced load flows in compliance with the booked capacities. To assess the feasibility of a booking, it is therefore necessary to check the feasibility of infinitely many nominations. As a result, deciding if a booking is feasible is a challenging mathematical problem, which we investigate in this dissertation.Our results range from passive networks, consisting of pipes only, to active networks, containing controllable elements to influence gas flows. Since the study of the latter naturally leads to a bilevel framework, we first consider some more general properties of bilevel optimization. For the case of linear bilevel optimization, we consider the hardness of validating the correctness of big-Ms often used in solving these problems via a single-level reformulation. We also derive a family of valid inequalities to be used in a bilevel-tailored branch-and-cut algorithm as a big-M-free alternative.We then turn to the study of feasible bookings. First, we present our results on passive networks, for which bilevel approaches are not required. A characterization of feasible bookings on passive networks is derived in terms of a finite set of nominations. While computing these nominations is a difficult task in general, we present polynomial complexity results for the special cases of tree-shaped or single-cycle passive networks. Finally, we consider networks with linearly modeled active elements. After obtaining a bilevel optimization model that allows us to determine the feasibility of a booking in this case, we derive various single-level reformulations to solve the problem. In addition, we obtain novel characterizations of feasible bookings on active networks, which generalize our characterization in the passive case. The performance of these various approaches is compared in a case study on two networks from the literature, one of which is a simplified version of the Greek gas network.
