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

Research output: Contribution to journalArticleScientificpeer-review

Researchers

  • Natashia Boland
  • Jeffrey Christiansen
  • Brian Dandurand
  • Andrew Eberhard
  • Jeff Linderoth
  • James Luedtke
  • Fabricio Oliveira

Research units

  • University of Wisconsin-Madison
  • Georgia Institute of Technology
  • RMIT University

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. This dual is widely used in decomposition methods for the solution of SMIPs. 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.

Details

Original languageEnglish
Pages (from-to)1312-1336
Number of pages25
JournalSIAM JOURNAL ON OPTIMIZATION
Volume28
Issue number2
Publication statusPublished - 2018
MoE publication typeA1 Journal article-refereed

    Research areas

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

ID: 20822324