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

2017/02/02 by Natashia Boland, Boland, Natashia, Jeffrey Christiansen +9
Business, Management and Accounting · Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #90Cxx #Capital Investment and Risk Analysis #FOS: Mathematics #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Supply Chain and Inventory Management #Transportation Planning and Optimization

paper · pdf · doi:10.48550/arxiv.1702.00880

openalex publication_date 2017/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Lagrangian cuts generated by batch to efficiently solve two-stage stochastic mixed-integer program
• Using Subproblem Objective Gaps in Inexact Augmented Lagrangian and ADMM Algorithms, with Applications to Stochastic Mixed Integer Programming
• On the ReLU Lagrangian Cuts for Stochastic Mixed Integer Programming
• Lagrangian Duality for Mixed-Integer Semidefinite Programming: Theory and Algorithms
• A computational study of cutting-plane methods for multi-stage stochastic integer programs