Integration of progressive hedging and dual decomposition in stochastic integer programs

被引：37

作者：

Guo, Ge ^{[1
]}

Hackebeil, Gabriel ^{[2
]}

Ryan, Sarah M. ^{[1
]}

Watson, Jean-Paul ^{[2
]}

Woodruff, David L. ^{[3
]}

机构：

[1] Iowa State Univ, Dept Ind & Mfg Syst Engn, Ames, IA 50011 USA

[2] Sandia Natl Labs, Discrete Math & Complex Syst Dept, Albuquerque, NM 87185 USA

[3] Univ Calif Davis, Grad Sch Management, Davis, CA 95616 USA

来源：

OPERATIONS RESEARCH LETTERS | 2015年 / 43卷 / 03期

基金：

美国能源部;

关键词：

Stochastic programming; Mixed-integer programming; Progressive hedging; Dual decomposition; Lower bounding; AGGREGATION;

D O I：

10.1016/j.orl.2015.03.008

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present a method for integrating the Progressive Hedging (PH) algorithm and the Dual Decomposition (DD) algorithm of Caroe and Schultz for stochastic mixed-integer programs. Based on the correspondence between lower bounds obtained with PH and DD, a method to transform weights from PH to Lagrange multipliers in DD is found. Fast progress in early iterations of PH speeds up convergence of DD to an exact solution. We report computational results on server location and unit commitment instances. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：311 / 316

页数：6

共 27 条

[21]

Ryan S. M., P IEEE 2013 IEEE POW

[22]

Sen S, 2005, HDBK OPER R, V12, P515

[23] A stochastic model for the unit commitment problem - Response [J].

Takriti, S ;

Birge, JR ;

Long, E .

IEEE TRANSACTIONS ON POWER SYSTEMS, 1996, 11 (03) :1507-1508

[24] L-SHAPED LINEAR PROGRAMS WITH APPLICATIONS TO OPTIMAL CONTROL AND STOCHASTIC PROGRAMMING [J].

VANSLYKE, RM ;

WETS, R .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1969, 17 (04) :638-+

[25] PySP: Modeling and solving stochastic programs in Python [J].

Watson J.-P. ;

Woodruff D.L. ;

Hart W.E. .

Mathematical Programming Computation, 2012, 4 (02) :109-149

[26] Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems [J].

Watson J.-P. ;

Woodruff D.L. .

Computational Management Science, 2011, 8 (4) :355-370

[27]

Wolsey L, 1988, INTEGER COMBINATORIA

← 1 2 3 →