Optimization Online


The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

Bram Verweij (bram***at***isye.gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
Anton Kleywegt (anton***at***isye.gatech.edu)
George Nemhauser (gnemhaus***at***isye.gatech.edu)
Alexander Shapiro (ashapiro***at***isye.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 first-stage integer variables. For each of the three problem classes, we use decomposition and branch-and-cut 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 near-optimal 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.289-333, 2003.


Entry Submitted: 09/04/2001
Entry Accepted: 09/04/2001
Entry Last Modified: 06/09/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society