The Sample Average Approximation Method for Stochastic Programs with Integer Recourse

Shabbir Ahmed (sahmedisye.gatech.edu)
Alexander Shapiro (ashapiroisye.gatech.edu)

Abstract: This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially fast as the sample size is increased. For fixed sample size, we describe statistical and deterministic bounding techniques to validate the quality of a candidate optimal solution. Preliminary computational experience with the method is reported.

Keywords: Stochastic programming, integer recourse, sample average approximation, branch and bound.

Category 1: Stochastic Programming

Category 2: Integer Programming (Other )

Category 3: Global Optimization (Stochastic Approaches )

Citation: Submitted for publication. Technical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology.

Download: [PDF]

Entry Submitted: 02/05/2002
Entry Accepted: 02/06/2002
Entry Last Modified: 02/05/2002

Modify/Update this entry