Back to Search
Start Over
Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making
- Source :
- Mathematical Programming. 196:597-640
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
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.<br />32 pages, 4 figures
- Subjects :
- Mathematical optimization
021103 operations research
Linear programming
General Mathematics
0211 other engineering and technologies
010103 numerical & computational mathematics
02 engineering and technology
01 natural sciences
Empirical distribution function
Bottleneck
Robust decision-making
Optimization and Control (math.OC)
FOS: Mathematics
Strong duality
Probability distribution
Ball (mathematics)
0101 mathematics
Uncertainty quantification
Mathematics - Optimization and Control
Software
Mathematics
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 196
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....fba22402480ea66a59ab8a471958e207