The impact of sampling methods on bias and variance in stochastic linear programs |
| |
Authors: | Michael B Freimer Jeffrey T Linderoth Douglas J Thomas |
| |
Institution: | (1) SignalDemand, Inc., 301 Howard Street, San Francisco, CA 94105, USA;(2) Department of Industrial and Systems Engineering, University of Wisconsin-Madison, 1513 University Ave., Madison, WI 53711, USA;(3) Smeal College of Business, The Pennsylvania State University, 463 Business Building, University Park, PA 16802-3603, USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|