Optimization Online


Combining Progressive Hedging with a Frank-Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming

Natashia Boland (natashia.boland***at***gmail.com)
Jeffrey Christiansen (s3507717***at***student.rmit.edu.au)
Brian Dandurand (brian.dandurand***at***rmit.edu.au)
Andrew Eberhard (andy.eberhard***at***rmit.edu.au)
Jeffrey Linderoth (linderoth***at***wisc.edu)
James Luedtke (jim.luedtke***at***wisc.edu)
Fabricio Oliveira (fabricio.oliveira***at***rmit.edu.au)

Abstract: We present a new primal-dual algorithm for computing the value of the Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing its nonanticipativity constraints. The algorithm relies on the well-known progressive hedging method, but unlike previous progressive hedging approaches for SMIP, our algorithm can be shown to converge to the optimal Lagrangian dual value. The key improvement in the new algorithm is an inner loop of optimized linearization steps, similar to those taken in the classical Frank-Wolfe method. Numerical results demonstrate that our new algorithm empirically outperforms the standard implementation of progressive hedging for obtaining bounds in SMIP.

Keywords: mixed-integer stochastic programming, Lagrangian duality, progressive hedging, Frank-Wolfe method

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 03/30/2016
Entry Accepted: 03/30/2016
Entry Last Modified: 06/14/2016

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