A New Scenario Decomposition Method for Large-Scale Stochastic Optimization

A novel parallel decomposition algorithm for large, multistage stochastic optimization problems that decomposes the problem into subproblems that correspond to scenarios and has promise for solving Stochastic programs that lie outside current capabilities.

Abstract

A novel parallel decomposition algorithm is developed for large, multistage stochastic optimization problems. The method decomposes the problem into subproblems that correspond to scenarios. The subproblems are modified by separable quadratic terms to coordinate the scenario solutions. Convergence of the coordination procedure is proven for linear programs. Subproblems are solved using a nonlinear interior point algorithm. The approach adjusts the degree of decomposition to fit the available hardware environment. Initial testing on a distributed network of workstations shows that an optimal number of computers depends upon the work per subproblem and its relation to the communication capacities. The algorithm has promise for solving stochastic programs that lie outside current capabilities.