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

• 成果类型: Article
• 署名作者: Xie, Weijun; Zhang, Jie; Ahmed, Shabbir
• 署名单位: Virginia Polytechnic Institute & State University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01627-0
• 发表日期: 2022
• 页码: 597-640
• 关键词: joint chance constraints; optimization; reformulations; CONVERGENCE; PROGRAMS; fair

摘要

In a bottleneck combinatorial problem, the objective is to minimize the highest cost of elements of a subset selected from the combinatorial solution space. 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, similar to the strong duality of linear programming, the alternative forms of the bottleneck combinatorial problems using clutters and blocking systems 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. That is, we study 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 conic program. Finally, we extend the proposed models and solution approaches to the distributionally robust Gamma-sum bottleneck combinatorial problem (DR Gamma BCP), where decision-makers are interested in minimizing the worst-case sum of Gamma highest costs of elements.