WIAS Preprint No. 1185, (2006)

Scenario reduction in stochastic programming with respect to discrepancy distances


  • Henrion, René
    ORCID: 0000-0001-5572-7213
  • Küchler, Christian
  • Römisch, Werner

2010 Mathematics Subject Classification

  • 90C15


  • Stochastic programming, chance constraints, two-stage, mixed-integer, scenario reduction, discrepancy, Kolmogorov metric




Discrete approximations to chance constraints and mixed-integer two-stage stochastic programs require moderately sized scenario sets. The relevant distances of (multivariate) probability distributions for deriving quantitative stability results for such stochastic programs are B-discrepancies, where the class B of Borel sets depends on their structural properties. Hence, the optimal scenario reduction problem for such models is stated with respect to B-discrepancies. In this paper, upper and lower bounds, and some explicit solutions for optimal scenario reduction problems are derived. In addition, we develop heuristic algorithms for determining nearly optimally reduced probability measures, discuss the case of the cell discrepancy (or Kolmogorov metric) in some detail and provide some numerical experience.

Appeared in

  • Comput. Optim. Appl., 43 (2009) pp. 67--93.

Download Documents