Aggregated Column Generation for Two-Stage Stochastic Mixed-Integer Programs
Abstract
Dantzig-Wolfe reformulation applied to two-stage stochastic mixed-integer programs (SMIP) has been shown empirically to yield a formulation with strong bounds that can be solved via column generation. However, the time to solve the restricted master problem grows significantly with the number of scenarios due to the increasing number of nonanticipativity constraints (NACs). Moreover, the associated high-dimensional dual space can cause the dual multipliers to oscillate between iterations, further slowing convergence. We propose an aggregated column generation framework for solving a Dantzig-Wolfe reformulation. Applied to SMIP, this method partitions the NACs into groups and replaces each group with a weighted surrogate constraint, leading to a reduced size and providing implicit stabilization by restricting the dual space. While aggregation leads to a relaxation, we develop two strategies for recovering the standard Dantzig-Wolfe reformulation bound. The first iteratively refines the partition by splitting groups that contain violated constraints. The second keeps the partition fixed and adaptively updates the aggregation weights. We prove convergence of the two approaches and study their computational performance on two benchmark problem classes.
Related
- Decomposition of Sparse Integer Programs via Nonlinear Edge Encodings and Column-and-Row Generation
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- Satisfiability and freezing in random integer programs
- On the Chvátal-Gomory Closure of Integer Quadratic Programs
- On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs
BibTeX
@misc{kothari2026aggregated,
title = {{Aggregated Column Generation for Two-Stage Stochastic Mixed-Integer Programs}},
author = {Harshit Kothari and James Luedtke and Luke Marshall},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19181},
eprint = {2610.19181},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19181},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Aggregated Column Generation for Two-Stage Stochastic Mixed-Integer Programs
AU - Harshit Kothari
AU - James Luedtke
AU - Luke Marshall
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.19181
UR - https://arxiv.org/abs/2610.19181
AB - Dantzig-Wolfe reformulation applied to two-stage stochastic mixed-integer programs (SMIP) has been shown empirically to yield a formulation with strong bounds that can be solved via column generation. However, the time to solve the restricted master problem grows significantly with the number of scenarios due to the increasing number of nonanticipativity constraints (NACs). Moreover, the associated high-dimensional dual space can cause the dual multipliers to oscillate between iterations, further slowing convergence. We propose an aggregated column generation framework for solving a Dantzig-Wolfe reformulation. Applied to SMIP, this method partitions the NACs into groups and replaces each group with a weighted surrogate constraint, leading to a reduced size and providing implicit stabilization by restricting the dual space. While aggregation leads to a relaxation, we develop two strategies for recovering the standard Dantzig-Wolfe reformulation bound. The first iteratively refines the partition by splitting groups that contain violated constraints. The second keeps the partition fixed and adaptively updates the aggregation weights. We prove convergence of the two approaches and study their computational performance on two benchmark problem classes.
ER -