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

^*Bu çalışma için yazışmadan sorumlu yazar

Argonne National Laboratory
The University of Chicago

Araştırma sonucu: Dergiye katkı › Makale › bilirkişi

49 Atıf (Scopus)

Özet

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.

Orijinal dil	İngilizce
Sayfa (başlangıç-bitiş)	252-258
Sayfa sayısı	7
Dergi	Operations Research Letters
Hacim	41
Basın numarası	3
DOI'lar	https://doi.org/10.1016/j.orl.2013.02.003
Yayın durumu	Yayınlandı - May 2013
Harici olarak yayınlandı	Evet

Finansman

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.

Finansörler	Finansör numarası
US Department of Energy	DE-AC02-06CH11357
Office of Science
Booth School of Business, University of Chicago

Belgeye Erişim

10.1016/j.orl.2013.02.003

Diğer Dosyalar ve Linkler

Link to publication in Scopus

Alıntı Yap

@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 - https://www.scopus.com/pages/publications/84874929547

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

Özet

Finansman

Belgeye Erişim

Diğer Dosyalar ve Linkler

Parmak izi

Alıntı Yap