Conditional Stochastic Decomposition: An Algorithmic Interface for Optimization and Simulation

Simulation and optimization are among the most commonly used elements in the 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, we 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 Renders decomposition of the problem. In this paper, our method is analytically verified and graphically illustrated. In addition, CSD is used to solve several test problems that have appeared in the literature. Our computational experience suggests that CSD may be particularly well suited for situations in which randomly generated observations are difficult to obtain.