Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs

• 成果类型: Article
• 署名作者: Gade, Dinakar; Hackebeil, Gabriel; Ryan, Sarah M.; Watson, Jean-Paul; Wets, Roger J. -B.; Woodruff, David L.
• 署名单位: United States Department of Energy (DOE); Sandia National Laboratories; Texas A&M University System; Texas A&M University College Station; Iowa State University; University of California System; University of California Davis
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1000-z
• 发表日期: 2016
• 页码: 47-67
• 关键词: dual decomposition; unit commitment; interdiction; MODEL

摘要

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 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.