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

被引：131

作者：

Gade, Dinakar ^{[1
]}

Hackebeil, Gabriel ^{[3
]}

Ryan, Sarah M. ^{[4
]}

Watson, Jean-Paul ^{[2
]}

Wets, Roger J. -B. ^{[5
]}

Woodruff, David L. ^{[5
]}

机构：

[1] Sabre Holdings, Southlake, TX 76092 USA

[2] Sandia Natl Labs, POB 5800, Albuquerque, NM 87185 USA

[3] Texas A&M Univ, College Stn, TX 77843 USA

[4] Iowa State Univ, Ames, IA 50011 USA

[5] Univ Calif Davis, Davis, CA 95616 USA

来源：

MATHEMATICAL PROGRAMMING | 2016年 / 157卷 / 01期

基金：

美国能源部;

关键词：

Stochastic mixed-integer programming; Decomposition algorithms; Lower bounding; DUAL DECOMPOSITION; UNIT COMMITMENT; INTERDICTION; MODEL;

D O I：

10.1007/s10107-016-1000-z

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：47 / 67

页数：21

共 42 条

[1] A finite branch-and-bound algorithm for two-stage stochastic integer programs [J].