Küchler Stability, Approximation, and Decomposition in Two- and Multistage Stochastic Programming

2009
ISBN: 978-3-8348-9399-4
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 178 Seiten, eBook

Reihe: Stochastic Programming

Christian Küchler studies various aspects of the stability of stochastic optimization problems as well as approximation and decomposition methods in stochastic programming. In particular, the author presents an extension of the Nested Benders decomposition algorithm related to the concept of recombining scenario trees.

Dr. Christian Küchler completed his doctoral thesis at the Humboldt University, Berlin. He currently works as a quantitative analyst at Landesbank Berlin AG.

Zielgruppe

Research

Autoren/Hrsg.

Küchler, Christian

Inhaltsverzeichnis

1;Preface;7
2;Contents;8
3;List of Figures;10
4;List of Tables;11
5;Index of Notation;12
6;Chapter 1 Introduction;14
6.1;1.1 Stochastic Programming Models;14
6.2;1.2 Approximations, Stability, and Decomposition;17
6.2.1;Approximations;17
6.2.2;Stability;18
6.2.3;Decomposition;19
6.3;1.3 Contributions;20
7;Chapter 2 Stability of Multistage Stochastic Programs;22
7.1;2.1 Problem Formulation;23
7.2;2.2 Continuity of the Recourse Function;26
7.3;2.3 Approximations;34
7.4;2.4 Calm Decisions;38
7.5;2.5 Stability;41
8;Chapter 3 Recombining Trees for Multistage Stochastic Programs;45
8.1;3.1 Problem Formulation and Decomposition;47
8.1.1;3.1.1 Nested Benders Decomposition;49
8.1.2;3.1.2 Cut Sharing;50
8.1.3;3.1.3 Recombining Scenario Trees;51
8.2;3.2 An Enhanced Nested Benders Decomposition;52
8.2.1;3.2.1 Cutting Plane Approximations;53
8.2.1.1;Optimality and Feasibility Cuts;54
8.2.1.2;Nested Benders Decomposition Algorithm;56
8.2.2;3.2.2 Dynamic Recombining of Scenarios;57
8.2.3;3.2.3 Upper Bounds;63
8.2.4;3.2.4 Extended Solution Algorithm;65
8.3;3.3 Construction of Recombining Trees;67
8.3.1;3.3.1 A Tree Generation Algorithm;69
8.3.1.1;Transition Probabilities;70
8.3.2;3.3.2 Consistency of the Tree Generation Algorithm;72
8.4;3.4 Case Study;89
8.4.1;3.4.1 A Power Scheduling Problem;89
8.4.2;3.4.2 Numerical Results;91
8.4.2.1;Cut Sharing;91
8.4.2.2;Aggregation of Decision Points;93
8.4.2.3;Dynamic Aggregation;94
8.5;3.5 Out-of-Sample Evaluation;95
8.5.1;3.5.1 Problem Formulation;96
8.5.2;3.5.2 Towards Feasible Solutions;97
8.5.2.1;Feasibility Restoration;98
8.5.3;3.5.3 Numerical Examples;101
8.5.3.1;Power Scheduling;102
8.5.3.2;Swing Option Exercising;104
9;Chapter 4 Scenario Reduction with Respect to Discrepancy Distances;109
9.1;4.1 Discrepancy Distances;110
9.2;4.2 On Stability of Two-Stage and ChanceConstrained Programs;112
9.2.1;Mixed-Integer Two-Stage Programs;113
9.2.2;Chance-Constrained Programs;116
9.3;4.3 Scenario Reduction;117
9.4;4.4 Bounds and Specific Solutions;118
9.4.1;4.4.1 Ordered Solution and Upper Bound;118
9.4.2;4.4.2 Lower Bound;122
9.5;4.5 The Inner Problem;125
9.5.1;4.5.1 Critical Index Sets;126
9.5.2;4.5.2 Reduced Critical Index Sets;127
9.5.2.1;A Sufficient Optimality Condition;127
9.5.3;4.5.3 Determining the Coefficients;128
9.5.4;4.5.4 Optimal Redistribution Algorithm;133
9.6;4.6 The Outer Problem;136
9.6.1;4.6.1 Revising Heuristics;136
9.6.2;4.6.2 A Glimpse on Low Discrepancy Sequences;139
9.6.3;4.6.3 A Branch and Bound Approach;139
9.6.3.1;Breadth-First Search Heuristics;141
9.7;4.7 Numerical Experience;143
9.7.1;Optimal Redistribution;144
9.7.2;Support Selection;145
9.7.3;Back to Stochastic Programming;147
9.8;4.8 Further Results;150
9.8.1;4.8.1 A Note on Extended Discrepancies;150
9.8.2;4.8.2 Mass Transportation and Clustering;152
9.8.2.1;Duality and Reduced Costs;152
9.8.2.2;Further Numerical Experience;155
9.8.3;4.8.3 An Estimation between Discrepancies;156
9.8.3.1;Upper Bound;158
9.8.3.2;Lower Bound;161
9.8.3.3;Determining the Polyhedral Singularity;162
10;Appendix;164
11;Bibliography;7

Stability of Multistage Stochastic Programs.- Recombining Trees for Multistage Stochastic Programs.- Scenario Reduction with Respect to Discrepancy Distances.

Leseproben

Chapter 3 Recombining Trees for Multistage Stochastic Programs (p. 32-33)

In order to solve multistage stochastic optimization problems by numerical methods, the underlying stochastic process is usually approximated by a process that takes only a ?nite number of values. Consequently, the approximating process can be represented by a scenario tree, where the nodes of the tree correspond to the possible realizations of the process and the tree structure is induced by the ?ltration generated by the process. Unfortunately, the number of nodes can grow exponentially as the number of time stages increases, and the corresponding optimization problem thus becomes quickly intractable. Hence, many problems of practical interest are represented by stochastic programming models that include only either a small number of time stages or a small number of scenarios.

Thereby, models with a small number of time stages either take only a short time horizon into account or they allow only for a very limited branching scheme of the scenario tree. Thus, such models may appear too simpli?ed to represent dynamic decision problems. In order to construct scenario trees that approximate the initial underlying stochastic process as best as possible by a small number of scenarios, certain approximation and scenario reduction techniques have been developed by P?ug (2001), Gröwe-Kuska et al. (2003), Heitsch and Römisch (2003), and Dupacová et al. (2003). Considering only few scenarios allows to solve problems with several thousands of time stages, see, e.g., the recent case study of Eichhorn et al. (2008). However, this reduction requires some compromise with regard to the representation of the underlying stochastic process.

An approach often used in practice, aiming to ?nd acceptable decisions along a concrete observation process, is to optimize with a rolling time horizon (cf., e.g., Sethi and Sorger (1991)). Thereby, a solution is constructed by solving a sequence of subproblems on small overlapping time intervals. However, decisions made by considering only a short time horizon will be myopic and thus generally not optimal whenever the optimization problem includes time-coupling constraints. The situation can be somewhat improved by ?nding suitable (shadow-) prices for those decision variables that a?ect the future costs.

A further approach to handle problems of larger dimensionality relies on recombining scenario trees. The probably best-known example is the Binomial Model of Stock Price Behaviour due to Cox, Ross, and Rubinstein (1979), where the node number of a binary scenario tree with T time stages decreases from 2T -1 to T(T +1)/2 by the recombination of scenarios. However, in a recombined node no information about the history of the parameter and the decision processes is available. Consequently, recombining scenario trees seem at ?rst sight not appropriate to solve optimization problems including time-coupling constraints.

Über Autor(innen)

Dr. Christian Küchler completed his doctoral thesis at the Humboldt University, Berlin. He currently works as a quantitative analyst at Landesbank Berlin AG.