  


The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study
Bram Verweij (bramisye.gatech.edu) Abstract: The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps. We present a detailed computational study of the application of the SAA method to solve three classes of stochastic routing problems. These stochastic problems involve an extremely large number scenarios and firststage integer variables. For each of the three problem classes, we use decomposition and branchandcut to solve the approximating problem within the SAA scheme. Our computational results indicate that the proposed method is successful in solving problems with up to 2^1694 scenarios to within an estimated 1% of optimality. Furthermore, a surprising observation is that the number of optimality cuts required to solve the approximating problem to optimality does not significantly increase with the size of the sample. Therefore, the observed computation times needed to find optimal solutions to the approximating problems grow only linearly with the sample size. As a result, we are able to find provably nearoptimal solutions to these difficult stochastic programs using only a moderate amount of computation time. Keywords: stochastic programming, stochastic routing, stochastic shortest path, stochastic traveling salesman Category 1: Stochastic Programming Category 2: Applications  OR and Management Sciences (Transportation ) Category 3: Integer Programming (Cutting Plane Approaches ) Citation: Computational and Applied Optimization, vol.24, pp.289333, 2003. Download: Entry Submitted: 09/04/2001 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  