Argonne National Laboratory

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