The Impact of Sampling Methods on Bias and Variance in Stochastic Linear Programs

Michael Freimer (mbf10psu.edu)
Doug Thomas (djt11psu.edu)
Jeff Linderoth (jtl3lehigh.edu)

Abstract: Two-stage 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 path optimization. Sample path optimization creates two kinds of objective function bias. First, 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. Second, if the stage-one decision from the solution to a sampled problem is implemented, the expected objective function value achieved is greater than the optimal objective value for the full problem. We investigate how two alternative sampling techniques, antithetic variates and Latin Hypercube sampling, affect these two biases relative to the alternative of drawing samples independently. We focus primarily on the first of these two types of bias, although we also characterize the bias in expected actual cost. For a simple example, we analytically express the reductions in bias obtained by these two sampling methods. We provide a general condition under which using antithetic variates reduces the bias of the expected optimal objective function value for the sampled problem. For seven test problems from the literature, we computationally investigate the bias impact of these sampling methods.

Keywords: stochastic programming; sample path optimization; antithetic variates; Latin Hypercube Sampling optimization; antithetic variates, Latin Hypercube sampling

Category 1: Stochastic Programming

Citation: Technical Report 05T-002, Department of Industrial and Systems Engineering, Lehigh University, 2005.

Download: [PDF]

Entry Submitted: 11/11/2005
Entry Accepted: 11/17/2005
Entry Last Modified: 10/16/2006

Modify/Update this entry