Optimization-Driven Scenario Grouping

Kevin Ryan (), Shabbir Ahmed (), Santanu S. Dey (), Deepak Rajan (), Amelia Musselman () and Jean-Paul Watson ()
Additional contact information
Kevin Ryan: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Shabbir Ahmed: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Santanu S. Dey: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Deepak Rajan: Lawrence Livermore National Laboratory, Livermore, California 94550
Amelia Musselman: Lawrence Livermore National Laboratory, Livermore, California 94550
Jean-Paul Watson: Sandia National Laboratory, Livermore, California 94550

INFORMS Journal on Computing, 2020, vol. 32, issue 3, 805-821

Abstract: Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems independently. We develop an approach that improves on these bounds by reinforcing a carefully chosen subset of nonanticipativity constraints, effectively placing scenarios into groups . Specifically, we formulate an optimization problem for grouping scenarios that aims to improve the bound by optimizing a proxy metric based on information obtained from evaluating a subset of candidate feasible solutions. We show that the proposed grouping problem is NP-hard in general, identify a polynomially solvable case, and present two formulations for solving the problem: a matching formulation for a special case and a mixed-integer programming formulation for the general case. We use the proposed grouping scheme as a preprocessing step for a particular scenario decomposition algorithm and demonstrate its effectiveness in solving standard test instances of two-stage 0–1 stochastic programs. Using this approach, we are able to prove optimality for all previously unsolved instances of a standard test set. Additionally, we implement this scheme as a preprocessing step for PySP, a publicly available and widely used implementation of progressive hedging, and compare this grouping approach with standard grouping approaches on large-scale stochastic unit commitment instances. Finally, the idea is extended to propose a finitely convergent algorithm for two-stage stochastic programs with a finite feasible region.

Keywords: stochastic programming; integer programming applications; computational methods (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0924 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:3:i:2020:p:805-821

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().