Sampling-Based Stochastic Linear Programming Methods

In this chapter, we study statistical methods for mean-risk two-stage stochastic linear programs (MR-SLP). We use the theoretical properties of the stochastic programming (SP) models derived in Chap. 2 and decomposition techniques from Chaps. 6 and 7 in the solution methods for MR-SLP. We study two main classical approaches, exterior sampling and interior sampling. Exterior sampling or Monte Carlo methods involve taking a sample and solving an approximation problem, and getting statistical bounds on key solution quantities. In this chapter, we study the basic sample average approximation (SAA) method for MR-SLP. Unlike exterior sampling methods, interior sampling involves sampling during the course of the algorithm. This requires a streamlined design of the algorithm within which sequential sampling is done to solve the approximation problem. We illustrate interior sampling with the basic stochastic decomposition (SD) method for MR-SLP. Since we place emphasis on algorithm computer implementation, we also discuss how to generate random samples from the instance data.