A Scenario Tree-Based Decomposition for Solving Multistage Stochastic Programs

Power generation based on renewable energy sources plays an important role in the development of a sustainable and environmentally friendly generation of energy, motivated by the finite nature of fossil energy sources and environmental pollution. In particular, wind energy is considered to be most promising to provide a substantial part of the electrical energy supply. But due to the fluctuating behavior of power production from renewable energies, especially caused by wind power production, new challenges are posed to the structure of power generation systems. In this context, we approach the question of how energy storages and flexible generation units may contribute to decouple fluctuating supply and demand, yielding a sustainable and cost efficient energy production. To this end, the problem is formulated as an optimization model including combinatorial, nonlinear, and stochastic aspects. By approximating the nonlinearities, we receive a stochastic multistage mixed-integer program. The aim of this thesis is the development of a solution algorithm which is capable to solve test instances sufficiently large to provide reliable results. This is accomplished by developing a decomposition approach based on splitting the corresponding scenario tree, enhanced by mixed integer programming techniques, such as primal methods and cutting plane generation.

The focus of this chapter is on the description of the power generation problem constituting the energy economical application of this thesis. In Section 2.1, we start with an introduction to the energy economical background exposing the issues arising from an increasing participation of regenerative energy to the electric energy supply. Subsequently, we give a description of the power supply problem studied in this thesis focusing on the application of energy storages in order to decouple fluctuating supply and demand in Section 2.2. In the power generation system, different power plants and energy storages are considered whose basic technical characteristics are presented in Section 2.3. Finally, in Section 2.4 we provide a survey on related literature concerning modeling and solution approaches of the problem.

The aim of this study is to analyze the potential of energy storages within a power generating system, including fluctuating energy supply. In this chapter we describe the mathematical modeling of the problem, taking technical as well as economical aspects into account.

This chapter is devoted to the algorithmic implementation of the SD-BB algorithm presented in Chapter 6. In order to make the algorithm successful, several ideas are developed which exploit either the specific properties of the algorithm or the characteristics of the S-OPGen problem.

In this chapter, we present a series of computational results for the solution of the D-OPGen and S-OPGen problem with the aim of documenting the performance of the solution approaches presented in the previous chapters. In Section 8.1, we start with a description of the problem instances considered for the computations by specifying the power generation system, followed by the presentation of the generated scenario trees. Subsequently, we computationally investigate the incorporation of facets determined for the stochastic switching polytope of Chapter 4 as cutting planes to a branchand-cut algorithm. The main focus of this chapter lies on the investigation on the computational behavior of the SD-BB algorithm whose development and implementation has been described in the previous two chapters. In this context, we perform a systematic calibration of the applied methods and parameters with the aim of obtaining general suggestions for the setting. On this basis the algorithm is applied to instances of larger size where we scale the basic characteristics which define a problem instance of the S-OPGen problem.

In this thesis, we have developed a novel scenario tree-based decomposition approach incorporated in a branch-and-bound framework for the solution of multistage stochastic mixed-integer programs. This study has been motivated by the real world problem arising in energy production when large amounts of fluctuating energy are fed into the public supply network. Due to the rising participation of electricity based on wind power, the potential of energy storages to decouple fluctuating supply and demand is of great interest.