Scenario reduction revisited: fundamental limits and guarantees

DOI10.1007/S10107-018-1269-1zbMATH Open1489.90090arXiv1701.04072OpenAlexW2579406944WikidataQ130022703 ScholiaQ130022703MaRDI QIDQ2118076FDOQ2118076

Kilian Schindler, Daniel Kuhn, Napat Rujeerapaiboon, Wolfram Wiesemann

Publication date: 22 March 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: The goal of scenario reduction is to approximate a given discrete distribution with another discrete distribution that has fewer atoms. We distinguish continuous scenario reduction, where the new atoms may be chosen freely, and discrete scenario reduction, where the new atoms must be chosen from among the existing ones. Using the Wasserstein distance as measure of proximity between distributions, we identify those $n$-point distributions on the unit ball that are least susceptible to scenario reduction, i.e., that have maximum Wasserstein distance to their closest $m$-point distributions for some prescribed $m<n$. We also provide sharp bounds on the added benefit of continuous over discrete scenario reduction. Finally, to our best knowledge, we propose the first polynomial-time constant-factor approximations for both discrete and continuous scenario reduction as well as the first exact exponential-time algorithms for continuous scenario reduction.

Full work available at URL: https://arxiv.org/abs/1701.04072

zbMATH Keywords

Wasserstein distance\(k\)-means clusteringscenario reductionconstant-factor approximation algorithm\(k\)-median clustering

Mathematics Subject Classification ID

Stochastic programming (90C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• Scenario reduction in stochastic programming
• Scenario reduction algorithms in stochastic programming
• Foundations of quantization for probability distributions
• A note on scenario reduction for two-stage stochastic programs
• Financial scenario generation for stochastic multi-stage decision processes as facility location problems
• Simulation and the Monte Carlo Method
• Second-order cone programming
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Quantitative Stability in Stochastic Programming: The Method of Probability Metrics
• A probability metrics approach for reducing the bias of optimality gap estimators in two-stage stochastic linear programming
• Stability analysis for stochastic programs
• Scenario tree generation for multiperiod financial optimization of optimal discretization
• A Dependent LP-Rounding Approach for the k-Median Problem
• Decision making under uncertainty in electricity markets
• An empirical analysis of scenario generation methods for stochastic optimization
• Approximations for Probability Distributions and Stochastic Optimization Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• Approximating \(k\)-median via pseudo-approximation
• The Planar k-Means Problem is NP-Hard
• Stability of $\varepsilon$-approximate Solutions to Convex Stochastic Programs
• Stability and sensitivity-analysis for stochastic programming
• A local search approximation algorithm for \(k\)-means clustering
• Data-driven risk-averse stochastic optimization with Wasserstein metric
• K-Adaptability in Two-Stage Robust Binary Programming
• Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
• Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

Cited In (5)

• A study of data-driven distributionally robust optimization with incomplete joint data under finite support
• Semi-discrete optimal transport: hardness, regularization and numerical solution
• Scenario generation by selection from historical data
• Mixed spatial and temporal decompositions for large-scale multistage stochastic optimization problems
• Frameworks and results in distributionally robust optimization

This page was built for publication: Scenario reduction revisited: fundamental limits and guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118076)