Combinatorial Network Flow Methods for Instationary Gas Flows and Gas Market Problems

Project description

In the second phase of this project, we gained a fine-grained view on the combinatorial complexity of gas flows and gas market problems. Partially building on a complete graph-theoretic characterization in terms of node-labeled minors of networks for which all capacity bookings lead to feasible flow nominations, we gave algorithms with asymptotically optimal approximation guarantee for the problem of choosing welfare optimal capacity bookings both for stationary and instationary gas flows, the former also leading to approximately efficient mechanisms for gas markets.

A central finding of our analysis is that requiring that all capacity bookings need to be satisfied fully in each time step is a main driver of the complexity of the problem. In view of the expected high utilization of gas networks in the future (e.g. through the addition of hydrogen) such a requirement seems not reasonable both in terms of complexity and in terms of fairness. For the third phase, this motivates us to study combinatorial network flow methods for stationary and instationary gas flows as well as gas market problems in which also a fractional allocation of demand (per time step) is allowed. More specifically, we will consider a model in which a set of welfare maximal bookings has to be selected, but the selected bookings can be distributed fractionally in time. Such a model leads to an interesting coupling of discrete decisions (which bookings are selected at all), fractional decisions (how the demand of the selected bookings are distributed over time), and the usual non-linearities arising from the gas physics. We will extend our investigation to online problems in which possible bookings are unknown beforehand, but arrive over time (in a random order). Finally, we will also study the fractional allocation of gas network capacities in a mechanism design framework.