Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making
From MaRDI portal
Abstract: This paper studies data-driven distributionally robust bottleneck combinatorial problems (DRBCP) with stochastic costs, where the probability distribution of the cost vector is contained in a ball of distributions centered at the empirical distribution specified by the Wasserstein distance. We study two distinct versions of DRBCP from different applications: (i) Motivated by the multi-hop wireless network application, we first study the uncertainty quantification of DRBCP (denoted by DRBCP-U), where decision-makers would like to have an accurate estimation of the worst-case value of DRBCP. The difficulty of DRBCP-U is to handle its max-min-max form. Fortunately, the alternative forms of the bottleneck combinatorial problems from their blockers allow us to derive equivalent deterministic reformulations, which can be computed via mixed-integer programs. In addition, by drawing the connection between DRBCP-U and its sampling average approximation counterpart under empirical distribution, we show that the Wasserstein radius can be chosen in the order of negative square root of sample size, improving the existing known results; and (ii) Next, motivated by the ride-sharing application, decision-makers choose the best service-and-passenger matching that minimizes the unfairness. This gives rise to the decision-making DRBCP (denoted by DRBCP-D). For DRBCP-D, we show that its optimal solution is also optimal to its sampling average approximation counterpart, and the Wasserstein radius can be chosen in a similar order as DRBCP-U. When the sample size is small, we propose to use the optimal value of DRBCP-D to construct an indifferent solution space and propose an alternative decision-robust model, which finds the best indifferent solution to minimize the empirical variance. We further show that the decision robust model can be recast as a mixed-integer program.
Recommendations
- Wasserstein distributionally robust shortest path problem
- An approach to the distributionally robust shortest path problem
- Bottleneck combinatorial optimization problems with fuzzy scenarios
- Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
- Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
Cites work
- A Probabilistic Model for Minmax Regret in Combinatorial Optimization
- A distributionally robust perspective on uncertainty quantification and chance constrained programming
- A note on the asymptotic behaviour of bottleneck problems
- Algorithms for the minmax regret path problem with interval data
- Ambiguous joint chance constraints under mean and dispersion information
- Asymptotic moments of the bottleneck assignment problem
- Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
- Bottleneck extrema
- Chance-constrained programming models and approximations for general stochastic bottleneck spanning tree problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls
- Convexity and decomposition of mean-risk stochastic programs
- Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
- Distributionally robust joint chance constraints with second-order moment information
- Distributionally robust optimization under moment uncertainty with application to data-driven problems
- Easy and hard bottleneck location problems
- Fundamentals of Wireless Communication
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Non-asymptotic confidence bounds for the optimal value of a stochastic program
- On deterministic reformulations of distributionally robust joint chance constrained optimization problems
- On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
- On the rate of convergence in Wasserstein distance of the empirical measure
- Possibilistic bottleneck combinatorial optimization problems with ill-known weights
- Quantifying distributional model risk via optimal transport
- Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization
- Risk-averse two-stage stochastic program with distributional ambiguity
- Robust Wasserstein profile inference and applications to machine learning
- The Min-Max Spanning Tree Problem and some extensions
- The random linear bottleneck assignment problem
- The stochastic bottleneck linear programming problem
- Variance-based regularization with convex objectives
Cited in
(4)- Special issue: Global solution of integer, stochastic and nonconvex optimization problems
- A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data
- Tight Probability Bounds with Pairwise Independence
- Distributionally Favorable Optimization: A Framework for Data-Driven Decision-Making with Endogenous Outliers
This page was built for publication: Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097653)
