Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 An Illustrative Example . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Stochastic Programs: General Formulation . . . . . . . . . . . . 15
1.3.1 Measures and Integrals . . . . . . . . . . . . . . . . . . . 16
1.3.2 Deterministic Equivalents . . . . . . . . . . . . . . . . . 25
1.4 Properties of Recourse Problems . . . . . . . . . . . . . . . . . 31
1.5 Properties of Probabilistic Constraints . . . . . . . . . . . . . . 41
1.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . 48
1.6.1 The Feasible Set and Solvability . . . . . . . . . . . . . 49
1.6.2 The Simplex Algorithm . . . . . . . . . . . . . . . . . . 59
1.6.3 Duality Statements . . . . . . . . . . . . . . . . . . . . . 64
1.6.4 A Dual Decomposition Method . . . . . . . . . . . . . . 70
1.7 Nonlinear Programming . . . . . . . . . . . . . . . . . . . . . . 75
1.7.1 The Kuhn–Tucker Conditions . . . . . . . . . . . . . . . 77
1.7.2 Solution Techniques . . . . . . . . . . . . . . . . . . . . 84
1.7.2.1 Cutting-plane methods . . . . . . . . . . . . . 84
1.7.2.2 Descent methods . . . . . . . . . . . . . . . . . 88
1.7.2.3 Penalty methods . . . . . . . . . . . . . . . . . 91
1.7.2.4 Lagrangian methods . . . . . . . . . . . . . . . 93
1.8 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . 97
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2 Dynamic Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2.1 The Bellman Principle . . . . . . . . . . . . . . . . . . . . . . . 105
2.2 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . 112
2.3 Deterministic Decision Trees . . . . . . . . . . . . . . . . . . . . 116
2.4 Stochastic Decision Trees . . . . . . . . . . . . . . . . . . . . . 119

2.6 Scenario Aggregation . . . . . . . . . . . . . . . . . . . . . . . . 129
2.6.1 Approximate Scenario Solutions . . . . . . . . . . . . . 136
2.7 The Value of Using a Stochastic Model . . . . . . . . . . . . . . 137
2.7.1 Comparing the Deterministic and Stochastic Objective
Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
2.7.2 Deterministic Solutions in the Event Tree . . . . . . . . 138
2.7.3 Expected Value of Perfect Information . . . . . . . . . . 140
2.8 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . 143
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
3 Recourse Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.1 Outline of Structure . . . . . . . . . . . . . . . . . . . . . . . . 147
3.2 The L-shaped Decomposition Method . . . . . . . . . . . . . . 149
3.2.1 Feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . 149
3.2.2 Optimality . . . . . . . . . . . . . . . . . . . . . . . . . 155
3.3 Regularized Decomposition . . . . . . . . . . . . . . . . . . . . 161
3.4 Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
3.4.1 The Jensen Lower Bound . . . . . . . . . . . . . . . . . 167
3.4.2 Edmundson–Madansky Upper Bound . . . . . . . . . . 168
3.4.3 Combinations . . . . . . . . . . . . . . . . . . . . . . . . 172
3.4.4 A Piecewise Linear Upper Bound . . . . . . . . . . . . . 173
3.5 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
3.5.1 Refinements of the “Wait-and-See”Solution . . . . . . . 178
3.5.2 Using the L-shaped Method within Approximation
Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
3.5.3 What is a Good Partition? . . . . . . . . . . . . . . . . 191
3.6 Simple Recourse . . . . . . . . . . . . . . . . . . . . . . . . . . 193
3.7 Integer First Stage . . . . . . . . . . . . . . . . . . . . . . . . . 197
3.7.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . . 203
3.7.2 Feasibility Cuts . . . . . . . . . . . . . . . . . . . . . . . 203
3.7.3 Optimality Cuts . . . . . . . . . . . . . . . . . . . . . . 203
3.7.4 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . 203
3.8 Stochastic Decomposition . . . . . . . . . . . . . . . . . . . . . 205
3.9 Stochastic Quasi-Gradient Methods . . . . . . . . . . . . . . . . 213
3.10 Solving Many Similar Linear Programs . . . . . . . . . . . . . . 218
3.10.1 Randomness in the Objective . . . . . . . . . . . . . . . 221
3.11 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . 221
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
4 Probabilistic Constraints . . . . . . . . . . . . . . . . . . . . . . 231

4.1 Joint Chance Constrained Problems . . . . . . . . . . . . . . . 233
4.2 Separate Chance Constraints . . . . . . . . . . . . . . . . . . . 235
4.3 Bounding Distribution Functions . . . . . . . . . . . . . . . . . 237
4.4 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . 245
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
5 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
5.1 Problem Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 249
5.1.1 Finding a Frame . . . . . . . . . . . . . . . . . . . . . . 250
5.1.2 Removing Unnecessary Columns . . . . . . . . . . . . . 251
5.1.3 Removing Unnecessary Rows . . . . . . . . . . . . . . . 252
5.2 Feasibility in Linear Programs . . . . . . . . . . . . . . . . . . . 253
5.2.1 A Small Example . . . . . . . . . . . . . . . . . . . . . . 260
5.3 Reducing the Complexity of Feasibility Tests . . . . . . . . . . 261
5.4 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . 262
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
6 Network Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 265
6.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
6.2 Feasibility in Networks . . . . . . . . . . . . . . . . . . . . . . . 268
6.2.1 Comparing the LP and Network Cases . . . . . . . . . . 276
6.3 Generating Relatively Complete Recourse . . . . . . . . . . . . 277
6.4 An Investment Example . . . . . . . . . . . . . . . . . . . . . . 279
6.5 Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
6.5.1 Piecewise Linear Upper Bounds . . . . . . . . . . . . . . 284
6.6 Project Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 290
6.6.1 PERT as a Decision Problem . . . . . . . . . . . . . . . 292
6.6.2 Introduction of Randomness . . . . . . . . . . . . . . . . 292
6.6.3 Bounds on the Expected Project Duration . . . . . . . . 293
6.6.3.1 Series reductions . . . . . . . . . . . . . . . . . 294
6.6.3.2 Parallel reductions . . . . . . . . . . . . . . . . 294
6.6.3.3 Disregarding path dependences . . . . . . . . . 294
6.6.3.4 Arc duplications . . . . . . . . . . . . . . . . . 295
6.6.3.5 Using Jensen’s inequality . . . . . . . . . . . . 295
6.7 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . 296
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298