Variance Reduction and Objective Function Evaluation in Stochastic Linear Programs

Planning under uncertainty requires the explicit representation of uncertain quantities within an underlying decision model. When the underlying model is a linear program, the representation of certain data elements as random variables results in a stochastic linear program (SLP). Precise evaluation of an SLP objective function requires the solution of a large number of linear programs, one for each possible combination of the random variables' outcomes. To reduce the effort required to evaluate the objective function, approximations, especially those derived from randomly sampled data, are often used. In this article, we explore a variety of variance-reduction techniques that can be used to improve the quality of the objective-function approximations derived from sampled data. These techniques are presented within the context of SLP objective-function evaluations. Computational results offering an empirical comparison of the level of variance reduction afforded by the various methods are included.