Optimization Online


Scenario grouping and decomposition algorithms for chance-constrained programs

Yan Deng(yandeng***at***umich.edu)
Shabbir Ahmed(shabbir.ahmed***at***isye.gatech.edu)
Jon Lee(jonxlee***at***umich.edu)
Siqian Shen(siqian***at***umich.edu)

Abstract: A lower bound for a finite-scenario chance-constrained problem is given by 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 larger subproblems. The quality of the bound depends on how the scenarios are grouped. 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, we derive a mixed-integer linear programming reformulation. We also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results show that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root node gaps and better performance of the scenario decomposition algorithm for chance-constrained 0-1 programs. Moreover, the bounds from feasible grouping solutions obtained after solving the optimal grouping model for 20%-50% of the total time are sufficiently tight, having gaps under 10% of the corresponding optimal grouping bounds. They outperform heuristic grouping bounds both in tightness and solving time, and can be significantly strengthened using larger group size.

Keywords: chance-constrained programming; quantile bounds; scenario grouping; mixed-integer programming; branch-and-cut; scenario decomposition

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 02/09/2017
Entry Accepted: 02/09/2017
Entry Last Modified: 02/09/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society