Optimization Online


Progressive Hedging Innovations for a Class of Stochastic Resource Allocation Problems

Jean-Paul Watson(jwatson***at***sandia.gov)
David Woodruff(dlwoodruff***at***ucdavis.edu)
David Strip(drstrip***at***sandia.gov)

Abstract: Progressive hedging (PH) is a scenario-based decomposition technique for solving stochastic programs. While PH has been successfully applied to a number of problems, a variety of issues arise when implementing PH in practice, especially when dealing with very difficult or large-scale mixed-integer problems. In particular, decisions must be made regarding the value of the penalty parameter rho, criteria for termination, and techniques for accelerating convergence. We investigate these issues in the context of a class of scenario-based resource allocation problem in which decision variables represent resources available at a cost and constraints enforce needs for sufficient combinations of resources. We introduce techniques for selecting rho in proportion to the unit-cost of the associated decision variable, a mathematically-based heuristic for setting the rho parameter, novel techniques for convergence acceleration, and methods for detecting and recovering from oscillatory behavior. The efficacy of these techniques is empirically assessed on two test cases: a difficult “laboratory” stochastic network flow problem and a largescale, real-world, robust spare parts procurement planning problem. Both test problems have integer variables in both stages. Additionally, we demonstrate that variable-specific rho values are more effective than traditional fixed rho values, and that the PH algorithm can serve as an effective heuristic even when the mathematical conditions for convergence are not respected.

Keywords: Stochastic Programming, Robust Optimization, Resource Allocation Problems

Category 1: Stochastic Programming

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Technical Report 2007-3722J, Sandia National Laboratories.

Download: [PDF]

Entry Submitted: 09/17/2008
Entry Accepted: 09/17/2008
Entry Last Modified: 09/17/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society