Optimization Online


On parallelizing dual decomposition in stochastic integer programming

Miles Lubin (mlubin***at***mit.edu)
Kipp Martin (kmartin***at***chicagobooth.edu)
Cosmin Petra (petra***at***mcs.anl.gov)
Burhannedin Sandıkçı (burhan***at***chicagobooth.edu)

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 \textit{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: stochastic programming, mixed-integer programming, column generation, dual decomposition, parallel computing, bundle methods

Category 1: Stochastic Programming

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Accepted for publication in Operations Research Letters. Formerly preprint ANL/MCS-P3037-0912, Argonne National Laboratory, October 2012.


Entry Submitted: 10/09/2012
Entry Accepted: 10/09/2012
Entry Last Modified: 02/10/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society