Optimization Online


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

Cong Han Lim (conghan***at***gatech.edu)
Jeff Linderoth (linderoth***at***wisc.edu)
James Luedtke (jim.luedtke***at***wisc.edu)
Stephen Wright (swright***at***cs.wisc.edu)

Abstract: 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.

Keywords: stochastic mixed-integer programming, subgradient methods, distributed optimization

Category 1: Stochastic Programming

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 11/28/2018
Entry Accepted: 12/01/2018
Entry Last Modified: 06/07/2019

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