Combining progressive hedging with a Frank--Wolfe method to compute Lagrangian dual bounds in stochastic mixed-integer programming

Boland, N, Christiansen, J, Dandurand, B, Eberhard, A, Linderoth, J, Luedtke, J and Pinheiro De Oliveira, F 2018, 'Combining progressive hedging with a Frank--Wolfe method to compute Lagrangian dual bounds in stochastic mixed-integer programming', SIAM Journal of Optimization, vol. 28, no. 2, pp. 1312-1336.


Document type: Journal Article
Collection: Journal Articles

Attached Files
Name Description MIMEType Size
n2006084138.pdf Published Version Click to show the corresponding preview/stream application/pdf; 680.82KB
Title Combining progressive hedging with a Frank--Wolfe method to compute Lagrangian dual bounds in stochastic mixed-integer programming
Author(s) Boland, N
Christiansen, J
Dandurand, B
Eberhard, A
Linderoth, J
Luedtke, J
Pinheiro De Oliveira, F
Year 2018
Journal name SIAM Journal of Optimization
Volume number 28
Issue number 2
Start page 1312
End page 1336
Total pages 25
Publisher Society for Industrial and Applied Mathematics
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.
Subject Optimisation
Applied Mathematics not elsewhere classified
Operations Research
Keyword(s) Mixed-integer stochastic programming
Lagrangian duality
Progressive hedging
Frank--Wolfe method
DOI - identifier 10.1137/16M1076290
Copyright notice © 2018 Society for Industrial and Applied Mathematics
ISSN 1052-6234
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Altmetric details:
Access Statistics: 17 Abstract Views, 22 File Downloads  -  Detailed Statistics
Created: Wed, 19 Sep 2018, 13:27:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us