Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
math.OC
Submitted: 2026-10-26
Updated: 2026-10-26
Comments: 26 pages, 4 figures
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: We describe an asynchronous parallel method to calculate Lagrangian bounds for mixed-integer stochastic programming problems.
Abstract
We describe an asynchronous parallel method to calculate Lagrangian bounds for mixed-integer stochastic programming problems. As in some prior work, we use a fully corrective Frank-Wolfe method on subproblems within a decomposition method, eventually optimizing subproblems for individual scenarios over the convex hulls of their integer-feasible vertices. However, instead of using progressive hedging as our decomposition algorithm, we employ an asynchronous projective hedging method. Like our earlier work on projective hedging, our algorithm need only solve a subset of the scenario subproblems at each iteration. Here, we further exploit the capabilities of projective hedging to create a parallel implementation capable of fully asynchronous operation. As we demonstrate empirically, this capability can lead to significant efficiency improvements when the subproblems are solved by Frank-Wolfe and have highly variable solve times.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise