On Parallelizing Dual Decomposition in Stochastic Integer Programming

TitleOn Parallelizing Dual Decomposition in Stochastic Integer Programming
Publication TypeJournal Article
Year of Publication2013
AuthorsLubin, M, Martin, K, Petra, CG, Sandikci, B
JournalOperations Research Letters
Volume41
Start Page252-258
Issue3
Date Published05/2013
Other NumbersANL/MCS-P3037-0912
Abstract

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

URLhttp://www.sciencedirect.com/science/article/pii/S0167637713000242
PDFhttp://www.mcs.anl.gov/papers/P3037-0912.pdf