TY - JOUR

T1 - The impact of sampling methods on bias and variance in stochastic linear programs

AU - Freimer, Michael B.

AU - Linderoth, Jeffrey T.

AU - Thomas, Douglas J.

N1 - Funding Information:
Acknowledgements We would like to thank Shane Henderson and Tito Homem-de-Mello for their helpful comments on earlier versions of this paper. The comments of two anonymous referees and the coordinating editor helped clarify the contribution and presentation significantly. The work of author Linderoth is supported in part by the Mathematical, Information and Computational Sciences subprogram of the Office of Science, US Department of Energy, under grant DE-FG02-09ER25869. The work of author Thomas is supported in part by the Smeal College of Business summer research grants. Computational resources are provided in part by equipment purchased by the NSF through the IGERT Grant DGE-9972780. We also acknowledge the computing resources and support of the Graduate Education and Research Services Group at Penn State.

PY - 2012/1

Y1 - 2012/1

N2 - Stochastic linear programs can be solved approximately by drawing a subset of all possible random scenarios and solving the problem based on this subset, an approach known as sample average approximation (SAA). The value of the objective function at the optimal solution obtained via SAA provides an estimate of the true optimal objective function value. This estimator is known to be optimistically biased; the expected optimal objective function value for the sampled problem is lower (for minimization problems) than the optimal objective function value for the true problem. We investigate how two alternative sampling methods, antithetic variates (AV) and Latin Hypercube (LH) sampling, affect both the bias and variance, and thus the mean squared error (MSE), of this estimator. For a simple example, we analytically express the reductions in bias and variance obtained by these two alternative sampling methods. For eight test problems from the literature, we computationally investigate the impact of these sampling methods on bias and variance. We find that both sampling methods are effective at reducing mean squared error, with Latin Hypercube sampling outperforming antithetic variates. For our analytic example and the eight test problems we derive or estimate the condition number as defined in Shapiro et al. (Math. Program. 94:1-19, 2002). We find that for ill-conditioned problems, bias plays a larger role in MSE, and AV and LH sampling methods are more likely to reduce bias.

AB - Stochastic linear programs can be solved approximately by drawing a subset of all possible random scenarios and solving the problem based on this subset, an approach known as sample average approximation (SAA). The value of the objective function at the optimal solution obtained via SAA provides an estimate of the true optimal objective function value. This estimator is known to be optimistically biased; the expected optimal objective function value for the sampled problem is lower (for minimization problems) than the optimal objective function value for the true problem. We investigate how two alternative sampling methods, antithetic variates (AV) and Latin Hypercube (LH) sampling, affect both the bias and variance, and thus the mean squared error (MSE), of this estimator. For a simple example, we analytically express the reductions in bias and variance obtained by these two alternative sampling methods. For eight test problems from the literature, we computationally investigate the impact of these sampling methods on bias and variance. We find that both sampling methods are effective at reducing mean squared error, with Latin Hypercube sampling outperforming antithetic variates. For our analytic example and the eight test problems we derive or estimate the condition number as defined in Shapiro et al. (Math. Program. 94:1-19, 2002). We find that for ill-conditioned problems, bias plays a larger role in MSE, and AV and LH sampling methods are more likely to reduce bias.

UR - http://www.scopus.com/inward/record.url?scp=84857192213&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84857192213&partnerID=8YFLogxK

U2 - 10.1007/s10589-010-9322-x

DO - 10.1007/s10589-010-9322-x

M3 - Article

AN - SCOPUS:84857192213

SN - 0926-6003

VL - 51

SP - 51

EP - 75

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 1

ER -