Conditional stochastic decomposition: An algorithmic interface for optimization and simulation

Simulation and optimization are among the most commonly used elements in the Operational Research OR toolkit. Often times, some of the data elements used to define an optimization problem are best described by random variables, yielding a stochastic program. If the distributions of the random variables cannot be specified precisely, one may have to resort to simulation to obtain observations of these random variables. In this paper, the authors present conditional stochastic decomposition (CSD), a method that may be construed as providing an algorithmic interface between simulation and optimization for the solution of stochastic linear programs with recourse. Derived from the concept of the stochastic decomposition of such problems, CSD uses randomly generated observations with a Benders decompositon of the problem. In this paper, the present method is analytically verified and graphically illustrated. In addition, CSD is used to solve several test problems that have appeared in the literature. The present computational experience suggests that CSD may be particularly well suited for situations in which randomly generated observations are difficult to obtain.