An embarrassingly parallel method for large-scale stochastic programs

Stochastic programming offers a flexible modeling framework for optimal decision-making problems under uncertainty. Most practical stochastic programming instances, however, quickly grow too large to solve on a single computer, especially due to memory limitations. This chapter reviews recent developments in solving large-scale stochastic programs, possibly with multiple stages and mixed-integer decision variables, and focuses on a scenario decomposition-based bounding method, which is broadly applicable as it does not rely on special problem structure and stands out as a natural candidate for implementation in a distributed fashion. In addition to discussing the method theoretically, this chapter examines issues related to a distributed implementation of the method on a modern computing grid. Using large-scale instances from the literature, this chapter demonstrates the potential of the method in obtaining high quality solutions to very large-scale stochastic programming instances within a reasonable time frame.