Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
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
- A Parallel Algebraic Multigrid Preconditioned Iterative Method Based on an MPI Process Grouping Strategy for Asynchronous Concurrent Execution of the Setup and Solve Phases
- Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry
- An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
- Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
- Unique ergodicity of projective cocycles over the 2D stochastic Navier-Stokes equations
BibTeX
@misc{eckstein2026asynchronous,
title = {{Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging}},
author = {Jonathan Eckstein and Jean-Paul Watson and David L. Woodruff},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36376},
eprint = {2610.36376},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36376},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
AU - Jonathan Eckstein
AU - Jean-Paul Watson
AU - David L. Woodruff
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36376
UR - https://arxiv.org/abs/2610.36376
AB - 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.
ER -