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 al e resolved, This gives rise to a need for stochastic prog ramming (SP) methods that create solutions that ale hedged against future uncertainty. The progressive hedging algorithm (PHA) of Rockafellar and Wets is a general method for SP. We cast the PHA ill 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, (C) 2001 Elsevier Science B.V. All rights reserved.