Optimization Online


Obtaining Lower Bounds from the Progressive Hedging Algorithm for Stochastic Mixed-Integer Programs

Dinakar Gade(dinakar.gade***at***gmail.com)
Gabriel Hackebeil(gabe.hackebeil***at***gmail.com)
Sarah M. Ryan(smryan***at***iastate.edu)
Jean-Paul Watson(jwatson***at***sandia.gov)
Roger J-B Wets(rjbwets***at***ucdavis.edu)
David L. Woodruff(DLWoodruff***at***ucdavis.edu)

Abstract: We present a method for computing lower bounds in the Progressive Hedging Algorithm (PHA) for two-stage and multi-stage stochastic mixed-integer programs. Computing lower bounds in the PHA allows one to assess the quality of the solutions generated by the algorithm contemporaneously. The lower bounds can be computed in any iteration of the algorithm by using dual prices that are calculated during execution of the standard PHA. We show that the best possible lower bound obtained using dual prices is as tight as the lower bound obtained using the Dual Decomposition method. We report computational results on stochastic unit commitment and stochastic server location problem instances, and explore the relationship between key PHA parameters and the quality of the resulting lower bounds. \keywords{Stochastic mixed-integer programming \and Decomposition algorithms \an

Keywords: Stochastic mixed-integer programming; Progressive Hedging; Lower Bounds

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Technical Report; Graduate School of Management; UC Davis; Davis CA 95616; October 11, 2013; revised January 21 2014 and May 2014

Download: [PDF]

Entry Submitted: 01/06/2015
Entry Accepted: 01/08/2015
Entry Last Modified: 01/06/2015

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 Optimization Society