On parallelizing dual decomposition in stochastic integer programming

被引：44

作者：

Lubin, Miles ^{[1
]}

Martin, Kipp ^{[2
]}

Petra, Cosmin G. ^{[1
]}

Sandikci, Burhaneddin ^{[2
]}

机构：

[1] Argonne Natl Lab, Math & Comp Sci Div, Argonne, IL 60439 USA

[2] Univ Chicago, Booth Sch Business, Chicago, IL 60637 USA

来源：

OPERATIONS RESEARCH LETTERS | 2013年 / 41卷 / 03期

关键词：

Stochastic programming; Mixed-integer programming; Column generation; Dual decomposition; Parallel computing; Bundle methods; BUNDLE; ALGORITHMS;

D O I：

10.1016/j.orl.2013.02.003

中图分类号：

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

学科分类号：

070105 [运筹学与控制论]; 120117 [社会管理工程];

摘要：

For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Came and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the master program by using structure-exploiting interior-point solvers. Our results demonstrate the potential for parallel speedup and the importance of regularization (stabilization) in the dual optimization. Load imbalance is identified as a remaining barrier to parallel scalability. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：252 / 258

页数：7

共 25 条

[1]

SCIP: solving constraint integer programs [J].

Achterberg, Tobias .

MATHEMATICAL PROGRAMMING COMPUTATION, 2009, 1 (01) :1-41

[2]

Amdahl G. M., 1967, P APR 18 20 1967 SPR, P483, DOI [10.1145/1465482.1465560, DOI 10.1145/1465482.1465560]

[3]

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

[4]

Comparison of bundle and classical column generation [J].

Briant, O. ;

Lemarechal, C. ;

Meurdesoif, Ph. ;

Michel, S. ;

Perrot, N. ;

Vanderbeck, F. .

MATHEMATICAL PROGRAMMING, 2008, 113 (02) :299-344

[5]

Dual decomposition in stochastic integer programming [J].

Caroe, CC ;

Schultz, R .

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

[6]

MA57 - A code for the solution of sparse symmetric definite and indefinite systems [J].

Duff, IS .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2004, 30 (02) :118-144

[7]

Solving two-stage stochastic programming problems with level decomposition [J].

Fabian, Csaba I. ;

Szoke, Zoltan .

COMPUTATIONAL MANAGEMENT SCIENCE, 2007, 4 (04) :313-353

[8]

Forrest John., CLP

[9]

About Lagrangian methods in integer optimization [J].

Frangioni, A .

ANNALS OF OPERATIONS RESEARCH, 2005, 139 (01) :163-193

[10]

Object-oriented software for quadratic programming [J].

Gertz, EM ;

Wright, SJ .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2003, 29 (01) :58-81

← 1 2 3 →