Parallelizing Subgradient Methods for the Lagrangian Dual in Stochastic Mixed-Integer Programming

The dual decomposition of stochastic mixed-integer programs can be solved by the projected subgradient algorithm. We show how to make this algorithm more amenable to parallelization in a master-worker model by describing two approaches, which can be combined in a natural way. The first approach partitions the scenarios into batches, and makes separate use of subgradient information for each batch. The second approach drops the requirement that evaluation of function and subgradient information is synchronized across the scenarios. We provide convergence analysis of both methods and evaluate their performance on two families of problems from SIPLIB, demonstrating the significant computational advantages that these two approaches (and their synthesis) can provide.

Article

Download

View Parallelizing Subgradient Methods for the Lagrangian Dual in Stochastic Mixed-Integer Programming