Progressive hedging innovations for a class of stochastic mixed‐integer resource allocation problems

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. Originally devised for problems possessing only continuous variables, PH has been successfully applied as a heuristic to solve multi‐stage stochastic programs with integer variables. However, a variety of critical issues arise in practice when implementing PH for the discrete case, especially in the context of very difficult or large‐scale mixed‐integer problems. Failure to address these issues properly results in either non‐convergence of the heuristic or unacceptably long run‐times. We 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 necessity and efficacy of our techniques is empirically assessed on a two‐stage stochastic network flow problem with integer variables in both stages.