Subtree decomposition for multistage stochastic programs

Abstract

An algorithm for solving multistage stochastic recourse problems is described. The scenario tree is decomposed using a cover of subtrees. The progressive hedging algorithm is used to ensure implementability across the entire tree. The approach leads to a class of methods which includes the original implementation of the progressive hedging algorithm. Computational testing indicates that the method can provide improved performance. The subtree decomposition methodology may be applied to a number of existing stochastic programming algorithms.