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

Published Online:

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. We also evaluate their performance on two families of problems from SIPLIB on a single server with 32 single-core worker processes, demonstrating that when the number of workers is high relative to the number of scenarios, these two approaches (and their synthesis) can significantly reduce running time.

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.