Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse

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...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2018-01, Vol.30 (1), p.57-70
Main Authors: van Ackooij, Wim, de Oliveira, Welington, Song, Yongjia
Format: Article
Language:English
Subjects:
Decomposition (Mathematics)
level decomposition
Linear programming
Methods
Problem solving
scenario reduction
Stochastic models
Stochastic programming
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 .
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.2017.0765