On parallelizing dual decomposition in stochastic integer programming

Miles Lubin; Kipp Martin; Cosmin G. Petra; Burhaneddin Sandikçi

doi:10.1016/j.orl.2013.02.003

On parallelizing dual decomposition in stochastic integer programming

Miles Lubin^*, Kipp Martin, Cosmin G. Petra, Burhaneddin Sandikçi

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

47 Citations (Scopus)

Abstract

For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Carøe 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.

Original language	English
Pages (from-to)	252-258
Number of pages	7
Journal	Operations Research Letters
Volume	41
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2013.02.003
Publication status	Published - May 2013
Externally published	Yes

Keywords

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

Access to Document

10.1016/j.orl.2013.02.003

Cite this

@article{4b4487347c0c4f0a979eddb7520e0a43,

title = "On parallelizing dual decomposition in stochastic integer programming",

abstract = "For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car{\o}e 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.",

keywords = "Bundle methods, Column generation, Dual decomposition, Mixed-integer programming, Parallel computing, Stochastic programming",

author = "Miles Lubin and Kipp Martin and Petra, {Cosmin G.} and Burhaneddin Sandik{\c c}i",

year = "2013",

month = may,

doi = "10.1016/j.orl.2013.02.003",

language = "English",

volume = "41",

pages = "252--258",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - On parallelizing dual decomposition in stochastic integer programming

AU - Lubin, Miles

AU - Martin, Kipp

AU - Petra, Cosmin G.

AU - Sandikçi, Burhaneddin

PY - 2013/5

Y1 - 2013/5

N2 - For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Carøe 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.

AB - For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Carøe 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.

KW - Bundle methods

KW - Column generation

KW - Dual decomposition

KW - Mixed-integer programming

KW - Parallel computing

KW - Stochastic programming

UR - http://www.scopus.com/inward/record.url?scp=84874929547&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2013.02.003

DO - 10.1016/j.orl.2013.02.003

M3 - Article

AN - SCOPUS:84874929547

SN - 0167-6377

VL - 41

SP - 252

EP - 258

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

On parallelizing dual decomposition in stochastic integer programming

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this