Stability, Approximation, and Decomposition in Two- and Multistage Stochastic Programming (eBook)

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

Preface 7
Contents 8
List of Figures 10
List of Tables 11
Index of Notation 12
Chapter 1 Introduction 14
1.1 Stochastic Programming Models 14
1.2 Approximations, Stability, and Decomposition 17
Approximations 17
Stability 18
Decomposition 19
1.3 Contributions 20
Chapter 2 Stability of Multistage Stochastic Programs 22
2.1 Problem Formulation 23
2.2 Continuity of the Recourse Function 26
2.3 Approximations 34
2.4 Calm Decisions 38
2.5 Stability 41
Chapter 3 Recombining Trees for Multistage Stochastic Programs 45
3.1 Problem Formulation and Decomposition 47
3.1.1 Nested Benders Decomposition 49
3.1.2 Cut Sharing 50
3.1.3 Recombining Scenario Trees 51
3.2 An Enhanced Nested Benders Decomposition 52
3.2.1 Cutting Plane Approximations 53
Optimality and Feasibility Cuts 54
Nested Benders Decomposition Algorithm 56
3.2.2 Dynamic Recombining of Scenarios 57
3.2.3 Upper Bounds 63
3.2.4 Extended Solution Algorithm 65
3.3 Construction of Recombining Trees 67
3.3.1 A Tree Generation Algorithm 69
Transition Probabilities 70
3.3.2 Consistency of the Tree Generation Algorithm 72
3.4 Case Study 89
3.4.1 A Power Scheduling Problem 89
3.4.2 Numerical Results 91
Cut Sharing 91
Aggregation of Decision Points 93
Dynamic Aggregation 94
3.5 Out-of-Sample Evaluation 95
3.5.1 Problem Formulation 96
3.5.2 Towards Feasible Solutions 97
Feasibility Restoration 98
3.5.3 Numerical Examples 101
Power Scheduling 102
Swing Option Exercising 104
Chapter 4 Scenario Reduction with Respect to Discrepancy Distances 109
4.1 Discrepancy Distances 110
4.2 On Stability of Two-Stage and ChanceConstrained Programs 112
Mixed-Integer Two-Stage Programs 113
Chance-Constrained Programs 116
4.3 Scenario Reduction 117
4.4 Bounds and Specific Solutions 118
4.4.1 Ordered Solution and Upper Bound 118
4.4.2 Lower Bound 122
4.5 The Inner Problem 125
4.5.1 Critical Index Sets 126
4.5.2 Reduced Critical Index Sets 127
A Sufficient Optimality Condition 127
4.5.3 Determining the Coefficients 128
4.5.4 Optimal Redistribution Algorithm 133
4.6 The Outer Problem 136
4.6.1 Revising Heuristics 136
4.6.2 A Glimpse on Low Discrepancy Sequences 139
4.6.3 A Branch and Bound Approach 139
Breadth-First Search Heuristics 141
4.7 Numerical Experience 143
Optimal Redistribution 144
Support Selection 145
Back to Stochastic Programming 147
4.8 Further Results 150
4.8.1 A Note on Extended Discrepancies 150
4.8.2 Mass Transportation and Clustering 152
Duality and Reduced Costs 152
Further Numerical Experience 155
4.8.3 An Estimation between Discrepancies 156
Upper Bound 158
Lower Bound 161
Determining the Polyhedral Singularity 162
Appendix 164
Bibliography 7

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.