Numerous planning problems can be formulated as multi-stage stochastic programs and many possess key discrete (integer) decision variables in one or more of the stages. Progressive hedging (PH) is a scenario-based decomposition technique that can be leveraged to solve such problems.

In this study, Professor David Woodruff and co-author Jean-Paul Watson from Sandia National Laboratory investigate these issues and describe algorithmic innovations in the context of a broad class of scenario-based resource allocation problem in which decision variables represent resources available at a cost and constraints enforce the need for sufficient combinations of resources. The authors assess the necessity and efficacy of these techniques empirically on a two-stage stochastic network flow problem with integer variables in both stages.