Exact Methods for Two-Stage Robust Optimization with Applications in Gas Networks

Description

Today, natural gas is one of the most important sources of energy and is regarded as a key instrument for achieving the politically set climate goals. Gas-fired power plants are valued as flexible buffers to compensate for fluctuations in electricity generation from renewable energy sources at short notice. Additionally, gas network operators face new challenges as a result of the liberalization of the European gas market. In the new entry-exit model, the gas network operators have to ensure that all possible market outcomes can be transported over the network. Hence, the operation of gas networks under uncertain conditions increasingly requires new aids for decision-making.

To this end, this thesis investigates a class of general two-stage robust optimization problems whose second-stage variables are uniquely determined by non-convex constraints. This structure occurs, e.g., in gas network operations under uncertainty.

Three general solution methods are developed for this problem class. The first two approaches use ideas from polynomial optimization to decide feasibility or infeasibility of a problem variant with an empty first stage. Both procedures use polynomial formulations that are approximated by semidefinite programs using the Lasserre relaxation hierarchy. The effectiveness of the methods is investigated on cyclic gas networks. It can be observed that often a low level of the Lasserre hierarchy is sufficient to decide robust feasibility or infeasibility.

The third approach is based on a transformation of the two-stage problem into a normal, single-stage optimization problem. To this end, several subproblems have to be solved whose optimal values form the right-hand side of the transformed problem. An additional aggregation step can significantly reduce the number of subproblems that have to be considered. For a practical application to real-world gas network instances, mixed-integer linear relaxations of the subproblems are developed. Finally, the performance of the approach is demonstrated by benchmarks on several gas network instances, including a realistic model of the Greek natural gas network. Overall, robust feasible solutions for large networks under uncertainty can be found within a short time.