Mahlke A Scenario Tree-Based Decomposition for Solving Multistage Stochastic Programs

With Application in Energy Production
2011
ISBN: 978-3-8348-9829-6
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 182 Seiten, eBook

Reihe: Stochastic Programming

Motivated by practical optimization problems occurring in energy systems with regenerative energy supply, Debora Mahlke formulates and analyzes multistage stochastic mixed-integer models. For their solution, the author proposes a novel decomposition approach which relies on the concept of splitting the underlying scenario tree into subtrees. Based on the formulated models from energy production, the algorithm is computationally investigated and the numerical results are discussed.

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

Zielgruppe

Research

Autoren/Hrsg.

Mahlke, Debora

Inhaltsverzeichnis

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

Über Autor(innen)

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