Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making

DOI10.1007/S10107-021-01627-0zbMATH Open1506.90189arXiv2003.00630OpenAlexW3132598941MaRDI QIDQ2097653FDOQ2097653

Authors: Weijun Xie, Jie Zhang, S. Ahmed 

Publication date: 14 November 2022

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

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.

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

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Minimax problems in mathematical programming (90C47) Mixed integer programming (90C11) Robustness in mathematical programming (90C17)

Cites Work

• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Distributionally robust joint chance constraints with second-order moment information
• Distributionally robust optimization under moment uncertainty with application to data-driven problems
• On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
• On the rate of convergence in Wasserstein distance of the empirical measure
• Convexity and decomposition of mean-risk stochastic programs
• Bottleneck extrema
• Fundamentals of Wireless Communication
• Easy and hard bottleneck location problems
• Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
• The Min-Max Spanning Tree Problem and some extensions
• Possibilistic bottleneck combinatorial optimization problems with ill-known weights
• Algorithms for the minmax regret path problem with interval data
• Non-asymptotic confidence bounds for the optimal value of a stochastic program
• The stochastic bottleneck linear programming problem
• A note on the asymptotic behaviour of bottleneck problems
• Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
• The random linear bottleneck assignment problem
• Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls
• Ambiguous joint chance constraints under mean and dispersion information
• Quantifying distributional model risk via optimal transport
• Robust Wasserstein profile inference and applications to machine learning
• Variance-based regularization with convex objectives
• A distributionally robust perspective on uncertainty quantification and chance constrained programming
• Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization
• A Probabilistic Model for Minmax Regret in Combinatorial Optimization
• Risk-averse two-stage stochastic program with distributional ambiguity
• Chance-constrained programming models and approximations for general stochastic bottleneck spanning tree problems
• On deterministic reformulations of distributionally robust joint chance constrained optimization problems
• Asymptotic moments of the bottleneck assignment problem

Cited In (4)

• A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data
• Special issue: Global solution of integer, stochastic and nonconvex optimization problems
• 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)