BBPH: Using progressive hedging within branch and bound to solve multi-stage stochastic mixed integer programs

详细信息    查看全文

• 作者：Jason Barnett^a ; ^{jpbarnett@math.ucdavis.edu} ; Jean-Paul Watson^b ; ^{jwatson@sandia.gov} ; David L. Woodruff^c ; ^{dlwoodruff@ucdavis.edu}
• 关键词：Stochastic programming ; Progressive hedging ; Branch and bound
• 刊名：Operations Research Letters
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：45
• 期：1
• 页码：34-39
• 全文大小：413 K
• 卷排序：45

文摘

Progressive hedging, though an effective heuristic for solving stochastic mixed integer programs (SMIPs), is not guaranteed to converge in this case. Here, we describe BBPH, a branch and bound algorithm that uses PH at each node in the search tree such that, given sufficient time, it will always converge to a globally optimal solution. In addition to providing a theoretically convergent “wrapper” for PH applied to SMIPs, computational results demonstrate that for some difficult problem instances branch and bound can find improved solutions after exploring only a few nodes.