Stochastic Programming ... get a brief survey by clicking here
SP Modeling? ... see Interfaces (1999), pages 33-61.
And be sure to click below for recent results
Topics covered in the following book
Stochastic Decomposition
by J.L. Higle and S. Sen, a monograph published by Kluwer Academic Publishers, 1996.
From the back cover ...
This book summarizes developments related to a class of
methods called Stochastic Decomposition (SD) algorithms,
which represent an important shift in the development of
optimization algorithms. Unlike traditional mathematical
programming algorithms, SD combines sampling approaches from
the statistical literature with traditional mathematical programming
constructs (e.g. decomposition, cutting planes etc.).
This marriage of statistical methodology within optimization algorithms
raises several novel issues which are explored throughout this book.
Furthermore, the use of sampled data in SD makes it extremely
flexible in its ability to accommodate various representations
of uncertainty, including situations in which outcomes/scenarios
can only be generated by an algorithm/simulation.
Finally, the authors report computational results with some of the
largest stochastic programs used in realistic applications. These
results (mathematical as well as computational) are the
``tip of the iceberg''. Future research will uncover
extensions of this methodology to a wider class of problems.
List of Topics in Stochastic Decomposition
(Kluwer Academic Publishers, 1996)
- 1. Two Stage Stochastic Linear Programs
- 1.1. Examples of Two Stage Stochastic Linear Programs
- 1.1.1. Capacity Expansion Planning: CEP1
- 1.1.2. Power Generation Planning: PGP2
- 1.1.3. Air Freight Scheduling: STORM
- 1.1.4. Telecommunications Network Planning: SSN
- 1.2. Properties of Two Stage Stochastic Linear Programs
- 1.3. Characteristics of Example Problems
- 1.4. Bibliographical Notes
- Appendix: CEP1 and PGP2 Data
- References
- 2. Sampling Within Stochastic Linear Programming
- 2.1. Kelley's Cutting Plane Algorithm
- 2.2. Successive Sample Mean Optimization
- 2.3. Issues Related to Sample-Based Optimization
- 2.4. Bibliographical Notes
- Appendix: Data Used in the Illustrative Example
- References
- 3. Foundations of Stochastic Decomposition
- 3.1. Stochastic Cutting Plane Method
- 3.2. Asymptotic Analysis of the SCP Algorithm
- 3.2.1. Preliminaries
- 3.2.2. Asymptotic Results for the SCP Method
- 3.3. Subproblem Approximation
- 3.4. A Basic Stochastic Decomposition Algorithm
- 3.5. Bibliographical Notes
- 4. Stabilizing Stochastic Decomposition
- 4.1. An Algorithm with Incumbent Solutions
- 4.2. A Regularized Master Program
- 4.3. Bibliographical Notes
- Appendix: Proof of Theorem 4.4
- References
- 5. Stopping Rules for Stochastic Decomposition
- 5.1. Termination Based on Asymptotic Properties
- 5.1.1. Identification of a Convergent Subsequence
- 5.1.2. Estimated Objective Value Stability
- 5.2. Termination Based on Error Bound Estimates
- 5.2.1. Statistical Estimation of Error Bounds
- 5.2.2. Error Bound Variability: A Conceptual Procedure
- 5.2.3. Error Bound Variability: A Bootstrap Procedure
- 5.3. Termination Based on Optimality Conditions
- 5.3.1. Summary of Optimality Conditions
- 5.3.2. Optimality Tests for the Case With Sampling
- 5.4. A Preliminary Test Prior to Termination
- 5.5. A Preliminary Comparison of Termination Criteria
- 5.6. Bibliographical Notes
- 6. Guidelines for Computer Implementation
- 6.1. Recursive Updates for Cut Formation
- 6.2. Cut Formation and Resampling
- 6.2.1. Forming Cuts
- 6.2.2. Updating Cuts
- 6.2.3. Resampling
- 6.3. Implementation of Statistical Optimality Tests
- 6.4. Bibliographical Notes
- 7. Illustrative Computational Experiments
- 7.1. Test Problem Characteristics
- 7.2. Performance Measures
- 7.3. Termination Based on Statistical Tests of Optimality
- 7.4. Regularized Master Program
- 7.5. Large Scale Implementation
- 7.6. Bibliographical Notes
- Glossary
Sen's Page