  


The Impact of Sampling Methods on Bias and Variance in Stochastic Linear Programs
Michael Freimer (mbf10psu.edu) Abstract: Twostage 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 stageone 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 05T002, Department of Industrial and Systems Engineering, Lehigh University, 2005. Download: [PDF] Entry Submitted: 11/11/2005 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  