A Scenario Tree-Based Decomposition for Solving Multistage Stochastic Programs (eBook)

Debora Mahlke received her Ph.D. in Mathematics from the Technische Universität Darmstadt where she currently works as a postdoctoral research associate.

Acknowledgments 7
Abstract 8
Contents 10
List of Figures 13
List of Tables 14
Chapter 1 Overview 16
Chapter 2 An Energy Production Problem 19
2.1 Introduction 19
2.2 Problem Description 20
2.3 Technical Background 23
2.3.1 Fossil-Fuel Power Plants 23
2.3.2 Energy Storages 24
2.4 Related Literature 25
Chapter 3 Mathematical Modeling 28
3.1 Deterministic Model 29
3.1.1 Sets and Parameters 29
3.1.2 Variables and E ciency Functions 32
3.1.3 Constraints 35
3.1.4 Objective Function 39
3.1.5 Linearization of the Nonlinear Functions 40
3.1.6 The D-OPGen Model 45
3.2 Stochastic Model 46
3.2.1 Basic Concepts in Stochastic Programming 46
3.2.2 The S-OPGen Model 48
Chapter 4 Polyhedral Study of Stochastic Switching Polytopes 52
4.1 Mathematical Formulation 52
4.2 Literature Overview 54
4.3 Polyhedral Investigations 55
4.4 Separation 68
Chapter 5 Primal Heuristics 70
5.1 Relax-and-Fix 70
5.2 A Rolling Horizon Approach to the D-OP Gen Problem 73
5.2.1 Approximation Strategies 76
5.2.2 Feasibility 79
5.3 An Approximate-and-Fix Approach to the S-OPGen Problem 84
Chapter 6 A Scenario Tree-Based Decomposition of Multistage Stochastic Mixed-Integer Problems 90
6.1 Motivation and Idea 91
6.2 Reformulation and Decomposition of the Stochastic Problem 94
6.3 A Scenario Tree-Based Decomposition Combined with Branch-and-Bound 97
6.4 Improving SD-BB by Applying Lagrangian Relaxation 103
6.4.1 Lagrangian Relaxation of Coupling Constraints 103
6.4.2 Integration of Lagrangian Relaxation into the SD-BB Algorithm 105
Chapter 7 Algorithmic Implementation 108
7.1 Decomposing a Scenario Tree 109
7.1.1 Finding an Optimal K-Subdivision 109
7.1.2 Rearranging an Optimal K-Subdivision 117
7.2 Branching 121
7.2.1 Variable Selection 121
7.2.2 Branching on Continuous Variables 126
7.3 Computing Lower Bounds 128
7.3.1 Generation of a First Lower Bound 129
7.3.2 Caching of Subproblems for the Computation of Lower Bounds 131
7.4 Computing Feasible Solutions 134
7.4.1 Primal Start Solution 134
7.4.2 Primal Solutions Based on Local Information 135
Chapter 8 Computational Results 138
8.1 Test Instances 139
8.1.1 Facilities in the Power Generation System 139
8.1.2 Stochastic Data 141
8.1.3 Test Instances for Parameter Tuning 142
8.2 Separation 143
8.3 Heuristics 147
8.3.1 Rolling Horizon Algorithm 147
8.3.2 Approximate-and-Fix Heuristic 156
8.4 SD-BB Algorithm 163
8.4.1 Decomposing the Scenario Tree 164
8.4.2 Computing a First Lower Bound 167
8.4.3 Heuristics 170
8.4.4 Branching 172
8.4.5 Accuracy 174
8.4.6 Solving Large Instances 176
Chapter 9 Conclusions 183
Bibliography 186
Akademischer Werdegang 194