Progressive hedging as a meta-heuristic applied to stochastic lot-sizing

In a great many situations, the data for optimization problems cannot be known with certainty and furthermore the decision process will take place in multiple time stages as the uncertainties are resolved. This gives rise to a need for stochastic programming (SP) methods that create solutions that are hedged against future uncertainty. The progressive hedging algorithm (PHA) of Rockafellar and Wets is a general method for SP. We cast the PHA in a meta-heuristic framework with the sub-problems generated for each scenario solved heuristically. Rather than using an approximate search algorithm for the exact problem as is typically the case in the meta-heuristic literature, we use an algorithm for sub-problems that is exact in its usual context but serves as a heuristic for our meta-heuristic. Computational results reported for stochastic lot-sizing problems demonstrate that the method is effective.