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

48 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

Funding

This work was supported in part by the US Department of Energy under Contract DE-AC02-06CH11357. This research used resources of the Laboratory Computing Resource Center at Argonne National Laboratory, which is supported by the Office of Science of the US Department of Energy under contract DE-AC02-06CH11357. Financial support from the University of Chicago Booth School of Business is also gratefully acknowledged. We thank Christoph Helmberg for correspondence regarding the ConicBundle package.

Funders	Funder number
US Department of Energy	DE-AC02-06CH11357
Office of Science
Booth School of Business, University of Chicago

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

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this