A novel L-shaped refinement chain cuts method for two-stage stochastic programs
Abstract
This paper introduces the L-shaped refinement chain cuts method, a novel decomposition approach for solving two-stage stochastic programs. The proposed method generalizes the classical L-shaped framework by exploiting refinement chains of scenarios, where sequences of increasingly refined scenario partitions are considered. At each refinement level, the full scenario set is partitioned into subgroups, and one subproblem is solved for each subgroup rather than for each individual scenario as in the classical L-shaped method. The proposed framework provides a unified decomposition scheme in which the classical multi-cut and single-cut L-shaped formulations arise as special cases. Theoretical convergence properties to the optimal solution of the original two-stage stochastic program are established at each refinement level. Furthermore, the relationships between consecutive refinement levels are characterized in terms of Benders cuts, leading to the development of an iterative refinement-based solution algorithm. The effectiveness of the proposed method is evaluated on a two-stage stochastic fixed-charge multicommodity network design problem under a mean-risk formulation. Computational experiments validate the benefits of the proposed approach and highlight its applicability to large-scale risk-averse stochastic optimization problems.
Related
- Riemannian Optimization on Unknown Manifolds via Stochastic Proximal Refinement
- A novel 2D diffusion model for composite domain with non-regularly shaped interface
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- Aggregated Column Generation for Two-Stage Stochastic Mixed-Integer Programs
- Regret-Based Scenario-Tree Construction for Multistage Stochastic Programs with Deterministic Constraints
BibTeX
@misc{hewitt2026novel,
title = {{A novel L-shaped refinement chain cuts method for two-stage stochastic programs}},
author = {Mike Hewitt and Francesca Maggioni and Andrea Spinelli},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.02469},
eprint = {2606.02469},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.02469},
}
RIS
TY - UNPB
TI - A novel L-shaped refinement chain cuts method for two-stage stochastic programs
AU - Mike Hewitt
AU - Francesca Maggioni
AU - Andrea Spinelli
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2606.02469
UR - https://arxiv.org/abs/2606.02469
AB - This paper introduces the L-shaped refinement chain cuts method, a novel decomposition approach for solving two-stage stochastic programs. The proposed method generalizes the classical L-shaped framework by exploiting refinement chains of scenarios, where sequences of increasingly refined scenario partitions are considered. At each refinement level, the full scenario set is partitioned into subgroups, and one subproblem is solved for each subgroup rather than for each individual scenario as in the classical L-shaped method. The proposed framework provides a unified decomposition scheme in which the classical multi-cut and single-cut L-shaped formulations arise as special cases. Theoretical convergence properties to the optimal solution of the original two-stage stochastic program are established at each refinement level. Furthermore, the relationships between consecutive refinement levels are characterized in terms of Benders cuts, leading to the development of an iterative refinement-based solution algorithm. The effectiveness of the proposed method is evaluated on a two-stage stochastic fixed-charge multicommodity network design problem under a mean-risk formulation. Computational experiments validate the benefits of the proposed approach and highlight its applicability to large-scale risk-averse stochastic optimization problems.
ER -