Scalable parallel computations for large-scale stochastic programming

Stochastic programming provides an effective framework for addressing decision problems under uncertainty in diverse fields. Stochastic programs incorporate many possible contingencies so as to proactively account for randomness in their input data; thus, they inevitably lead to very large optimization programs. Consequently, efficient algorithms that can exploit the capabilities of advanced computing technologies – including multiprocessor computers – become imperative to solve large-scale stochastic programs. This paper surveys the state-of-the-art in parallel algorithms for stochastic programming. Algorithms are reviewed, classified and compared. Qualitative comparisons are based on the applicability, scope, ease of implementation, robustness and reliability of each algorithm, while quantitative comparisons are based on the computational performance of algorithmic implementations on multiprocessor systems. Emphasis is placed on the potential of parallel algorithms to solve large-scale stochastic programs.