Scenario reduction revisited: fundamental limits and guarantees

DOI10.1007/S10107-018-1269-1MaRDI QIDQ2118076zbMATH OpenOpenAlexWikidataFDO

Authors Napat Rujeerapaiboon, Kilian Schindler, Daniel Kuhn, Wolfram Wiesemann

Publication date 22 March 2022

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

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)

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.

Recommendations

• Scenario reduction in stochastic programming
• Scenario reduction in stochastic programming with respect to discrepancy distances
• Scenario reduction algorithms in stochastic programming
• Scenario Reduction Techniques in Stochastic Programming
• Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming

Cites work

• scientific article; zbMATH DE number 2130678 (Why is no real title available?)
• scientific article; zbMATH DE number 1746287 (Why is no real title available?)
• A dependent LP-rounding approach for the \(k\)-median problem
• A local search approximation algorithm for \(k\)-means clustering
• A note on scenario reduction for two-stage stochastic programs
• A probability metrics approach for reducing the bias of optimality gap estimators in two-stage stochastic linear programming
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• An empirical analysis of scenario generation methods for stochastic optimization
• Approximating \(k\)-median via pseudo-approximation
• Approximations for Probability Distributions and Stochastic Optimization Problems
• Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls
• Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
• Data-driven risk-averse stochastic optimization with Wasserstein metric
• Decision making under uncertainty in electricity markets
• Financial scenario generation for stochastic multi-stage decision processes as facility location problems
• Foundations of quantization for probability distributions
• Least squares quantization in PCM
• Local Search Heuristics for k-Median and Facility Location Problems
• NP-hardness of Euclidean sum-of-squares clustering
• Quantitative Stability in Stochastic Programming: The Method of Probability Metrics
• Scenario reduction algorithms in stochastic programming
• Scenario reduction in stochastic programming
• Scenario tree generation for multiperiod financial optimization of optimal discretization
• Second-order cone programming
• Simulation and the Monte Carlo Method
• Stability analysis for stochastic programs
• Stability and sensitivity-analysis for stochastic programming
• Stability of $\varepsilon$-approximate Solutions to Convex Stochastic Programs
• The Planar k-Means Problem is NP-Hard
• Toeplitz and circulant matrices: a review.
• \(K\)-adaptability in two-stage robust binary programming

Cited in

(6)

• A study of data-driven distributionally robust optimization with incomplete joint data under finite support
• On the error of approximation by means of scenario trees with depth 1
• 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)