Introduction to Stochastic Programming (eBook)

Preface 8
Preface to the First Edition 12
Contents 16
Notation 22
Part I Models 28
1 Introduction and Examples 29
1.1 A Farming Example and the News Vendor Problem 30
a. The farmer's problem 30
b. A scenario representation 32
c. General model formulation 36
d. Continuous random variables 37
e. The news vendor problem 41
1.2 Financial Planning and Control 46
1.3 Capacity Expansion 54
1.4 Design for Manufacturing Quality 61
1.5 A Routing Example 66
a. Presentation 66
b. Wait-and-see solutions 68
c. Expected value solution 69
d. Recourse solution 70
e. Other random variables 72
f. Chance-constraints 73
1.6 Other Applications 74
2 Uncertainty and Modeling Issues 81
2.1 Probability Spaces and Random Variables 81
2.2 Deterministic Linear Programs 83
2.3 Decisions and Stages 83
2.4 Two-Stage Program with Fixed Recourse 85
a. Fixed distribution pattern, fixed demand,ri, vj, tij stochastic 88
b. Fixed distribution pattern, uncertain demand 89
c. Uncertain demand, variable distribution pattern 90
d. Stages versus periods Two-stage versus multistage
2.5 Random Variables and Risk Aversion 92
2.6 Implicit Representation of the Second Stage 94
a. A closed form expression is available for Q(x) 95
b. For a given x, Q(x) is computable 96
2.7 Probabilistic Programming 97
a. Deterministic linear equivalent: a direct case 97
b. Deterministic linear equivalent: an indirect case 98
c. Deterministic nonlinear equivalent: the case of random constraint coefficients 99
2.8 Modeling Exercise 100
a. Presentation 100
b. Discussion of solutions 102
2.9 Alternative Characterizations and Robust Formulations 110
2.10 Relationship to Other Decision-Making Models 113
a. Statistical decision theory and decision analysis 113
b. Dynamic programming and Markov decision processes 115
c. Machine learning and online optimization 116
d. Optimal stochastic control 117
e. Summary 119
2.11 Short Reviews 120
a. Linear programming 120
b. Duality for linear programs 122
c. Nonlinear programming and convex analysis 123
Part II Basic Properties 127
3 Basic Properties and Theory 128
3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 128
a. Formulation 128
b. Discrete random variables 130
c. General cases 134
d. Special cases: relatively complete, complete,and simple recourse 138
e. Optimality conditions and duality 140
f. Stability and nonanticipativity 143
3.2 Probabilistic or Chance Constraints 149
a. General case 149
b. Probabilistic constraints with discrete random variables 155
3.3 Stochastic Integer Programs 160
a. Recourse problems 160
b. Simple integer recourse 165
c. Probabilistic constraints 171
3.4 Multistage Stochastic Programs with Recourse 174
3.5 Stochastic Nonlinear Programs with Recourse 181
4 The Value of Information and the Stochastic Solution 187
4.1 The Expected Value of Perfect Information 187
4.2 The Value of the Stochastic Solution 189
4.3 Basic Inequalities 190
4.4 The Relationship between EVPI and VSS 191
a. EVPI = 0 and VSS =0 192
b. VSS = 0 and EVPI=0 193
4.5 Examples 194
4.6 Bounds on EVPI and VSS 195
Part III Solution Methods 202
5 Two-Stage Recourse Problems 203
5.1 The L-Shaped Method 204
a. Optimality cuts 206
b. Feasibility cuts 213
c. Proof of convergence 218
d. The multicut version 220
5.2 Regularized Decomposition 224
5.3 The Piecewise Quadratic Form of the L-shaped Methods 232
5.4 Bunching and Other Efficiencies 239
a. Full decomposability 240
b. Bunching 241
5.5 Basis Factorization and Interior Point Methods 244
5.6 Inner Linearization Methods and Special Structures 259
5.7 Simple and Network Recourse Problems 264
5.8 Methods Based on the Stochastic Program Lagrangian 275
5.9 Additional Methods and Complexity Results 284
6 Multistage Stochastic Programs 286
6.1 Nested Decomposition Procedures 287
6.2 Quadratic Nested Decomposition 297
6.3 Block Separability and Special Structure 303
6.4 Lagrangian-Based Methods for Multiple Stages 305
7 Stochastic Integer Programs 309
7.1 Stochastic Integer Programs and LP-Relaxation 309
7.2 First-stage Binary Variables 311
a. Improved optimality cuts 314
b. Example with continuous random variables 319
7.3 Second-stage Integer Variables 322
a. Looking in the space of tenders 323
b. Discontinuity points 325
c. Algorithm 326
7.4 Reformulation 332
a. Difficulties of reformulation in stochastic integer programs 332
b. Disjunctive cuts 334
c. First-stage dependence 336
d. An algorithm 337
7.5 Simple Integer Recourse 339
a. restricted to be integer 342
b. The case where S=1, not integral 345
7.6 Cuts Based on Branching in the Second Stage 346
a. Feasibility cuts 346
b. Optimality cuts 349
7.7 Extensive Forms and Decomposition 351
7.8 Short Reviews 354
a. Branch-and-bound 354
b. A simple example of valid inequalities 355
c. Disjunctive cuts 356
Part IV Approximation and Sampling Methods 359
8 Evaluating and Approximating Expectations 360
8.1 Direct Solutions with Multiple Integration 361
8.2 Discrete Bounding Approximations 365
8.3 Using Bounds in Algorithms 371
8.4 Bounds in Chance-Constrained Problems 376
8.5 Generalized Bounds 382
a. Extensions of basic bounds 382
b. Bounds based on separable functions 386
c. General-moment bounds 391
8.6 General Convergence Properties 400
9 Monte Carlo Methods 407
9.1 Sample Average Approximation and Importance Samplingin the L-Shaped Method 408
9.2 Stochastic Decomposition 413
9.3 Stochastic Quasi-Gradient Methods 417
9.4 Sampling Methods for Probabilistic Constraints and Quantiles 422
9.5 General Results for Sample Average Approximation and Sequential Sampling 427
10 Multistage Approximations 434
10.1 Extensions of the Jensen and Edmundson-Madansky Inequalities 435
10.2 Bounds Based on Aggregation 439
10.3 Scenario Generation and Distribution Fitting 443
10.4 Multistage Sampling and Decomposition Methods 449
10.5 Approximate Dynamic Programming and Special Cases 453
a. Network revenue management 455
b. Vehicle allocation problems 456
c. Piecewise-linear separable bounds 458
d. Nonlinear bounds and a production planning example 461
e. Extensions 463
Sample Distribution Functions 466
A.1 Discrete Random Variables 466
A.2 Continuous Random Variables 467
References 468
Author Index 487
Subject Index 492