论文标题
分配强大的瓶颈组合问题：不确定性量化和强大的决策
Distributionally Robust Bottleneck Combinatorial Problems: Uncertainty Quantification and Robust Decision Making
论文作者
论文摘要
本文研究了数据驱动的分布在稳健的瓶颈组合问题（DRBCP），并具有随机成本，其中成本矢量的概率分布包含在以Wasserstein距离指定的经验分布的分布球中。我们研究了来自不同应用的两个不同版本的DRBCP：（i）由多跳无线网络应用激励，我们首先研究了DRBCP的不确定性量化（由DRBCP-U表示），在此决策者希望对DRBCP最差的案例值进行准确的估计。 DRBCP-U的困难是处理其最大最大最大形式。幸运的是，瓶颈组合问题的替代形式使我们能够得出同等的确定性重新纠正，可以通过混合企业计划计算。此外，通过在经验分布下绘制DRBCP-U及其采样平均近似对应物之间的连接，我们表明可以按样本大小的负平方根的顺序选择Wasserstein Radius，从而改善现有的已知结果； （ii）接下来，在乘车共享应用程序的推动下，决策者选择了最好的服务和乘客匹配，从而最大程度地减少了不公平性。这引起了决策DRBCP（由DRBCP-D表示）。对于DRBCP-D，我们表明其最佳解决方案对于其采样平均近似对应物也是最佳的，并且可以以与DRBCP-U相似的顺序选择Wasserstein Radius。当样本量很小时，我们建议使用DRBCP-D的最佳值来构建无关紧要的解决方案空间，并提出替代性决策模型，该模型找到了最佳的无冷漠解决方案，以最大程度地减少经验方差。我们进一步表明，鲁棒模型可以作为混合计划的计划重新铸造。
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.
