Scenario Grouping and Decomposition Algorithms for Chance-Constrained Programs

Yan Deng (), Huiwen Jia, Shabbir Ahmed, Jon Lee and Siqian Shen ()
Additional contact information
Yan Deng: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Huiwen Jia: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Shabbir Ahmed: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Jon Lee: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Siqian Shen: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

INFORMS Journal on Computing, 2021, vol. 33, issue 2, 757-773

Abstract: A lower bound for a finite-scenario-based chance-constrained program is the quantile value corresponding to the sorted optimal objective values of scenario subproblems. This quantile bound can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. The quality of the bound depends on how the scenarios are grouped. In this paper, we formulate a mixed-integer bilevel program that optimally groups scenarios to tighten the quantile bounds. For general chance-constrained programs, we propose a branch-and-cut algorithm to optimize the bilevel program, and for chance-constrained linear programs, a mixed-integer linear-programming reformulation is derived. We also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results demonstrate that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root-node gaps and better performance of scenario decomposition for solving chance-constrained 0-1 programs. Also, the optimal grouping bounds can be greatly strengthened using larger group size. Summary of Contribution: Chance-constrained programs are in general NP-hard but widely used in practice for lowering the risk of undesirable outcomes during decision making under uncertainty. Assuming finite scenarios of uncertain parameter, chance-constrained programs can be reformulated as mixed-integer linear programs with binary variables representing whether or not the constraints are satisfied in corresponding scenarios. A useful quantile bound for solving chance-constrained programs can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. In this paper, we develop algorithms for optimally and heuristically grouping scenarios to tighten the quantile bounds. We aim to improve both the computation and solution quality of a variety of chance-constrained programs formulated for different Operations Research problems.

Keywords: chance-constrained programming; quantile bounds; scenario grouping; mixed-integer programming; branch-and-cut; scenario decomposition (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0970 (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:33:y:2021:i:2:p:757-773

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