Integration of progressive hedging and dual decomposition in stochastic integer programs

被引：35

作者：

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 条

[1]

Birge JR, 2011, SPRINGER SER OPER RE, P3, DOI 10.1007/978-1-4614-0237-4

[2]

Caroe C.C., 1995, TECHNICAL REPORT

[3] Dual decomposition in stochastic integer programming [J].

Caroe, CC ;

Schultz, R .

OPERATIONS RESEARCH LETTERS, 1999, 24 (1-2) :37-45

[4] A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem [J].

Carrion, Miguel ;

Arroyo, Jose M. .

IEEE TRANSACTIONS ON POWER SYSTEMS, 2006, 21 (03) :1371-1378

[5]

Ela E., 2011, POW EN SOC GEN M IEE

[6] Solving Stochastic Transportation Network Protection Problems Using the Progressive Hedging-based Method [J].

Fan, Yueyue ;

Liu, Changzheng .

NETWORKS & SPATIAL ECONOMICS, 2010, 10 (02) :193-208

[7] Solution sensitivity-based scenario reduction for stochastic unit commitment [J].

Feng Y. ;

Ryan S.M. .

Computational Management Science, 2016, 13 (1) :29-62

[8]

Gade D., 2014, TECHNICAL REPORT

[9] Pyomo: modeling and solving mathematical programs in Python']Python [J].

Hart, William E. ;

Watson, Jean-Paul ;

Woodruff, David L. .

MATHEMATICAL PROGRAMMING COMPUTATION, 2011, 3 (03) :219-260

[10]

Helmberg C., The ConicBundle library for convex optimization

← 1 2 3 →