Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse
Wim van Ackooij, Welington de Oliveira, Yongjia Song
INFORMS Journal on Computing · 2018 · Volume 30 · Issue 1
Abstract
We present a computational study of several strategies to solve two-stage stochastic linear programs by integrating the adaptive partition-based approach with level decomposition. A partition-based formulation is a relaxation of the original stochastic program, obtained by aggregating variables and constraints according to a scenario partition. Partition refinements are guided by the optimal second-stage dual vectors computed at certain first-stage solutions. The proposed approaches rely on the level decomposition with on-demand accuracy to dynamically adjust partitions until an optimal solution is found. Numerical experiments on a large set of test problems including instances with up to one hundred thousand scenarios show the effectiveness of the proposed approaches. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0765 .
Keywords
stochastic programming, scenario reduction, level decomposition
Enable JavaScript for citation tools and additional paper interactions.