A Solution Approach to Distributionally Robust Joint-Chance-Constrained Assignment Problems
A Solution Approach to Distributionally Robust Joint-Chance-Constrained Assignment Problems
复制标题
DOI：
10.1287/ijoo.2021.0060
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Shanshan Wang;Jinlin Li;Sanjay Mehrotra
中科院分区：
文献类型：
--
作者：
Shanshan Wang;Jinlin Li;Sanjay Mehrotra
本文研究了机会约束指派问题（CAP）及其分布鲁棒对应问题DR-CAP。我们提出了一种技术，估计大M在这样一个制定，利用的模糊集。我们考虑一个0-1双线性背包集，发展有效的CAP和DR-CAP不等式。这被推广到联合机会约束问题。本文还提出了一个概率割框架来求解DR-CAP问题。从使用真实的医院手术数据获得的问题实例的计算研究表明，所开发的技术允许我们解决某些模型实例，并减少其他的计算时间。在DR-CAP模型中使用Wasserstein模糊集比在样本平均近似技术中通过增加样本大小更显著地改善了满足机会约束的样本外性能。DR-CAP模型实例的求解时间与CAP实例的求解时间具有相同的数量级。这一发现很重要，因为当约束中的系数是随机的时，机会约束优化模型很难求解。
We study the assignment problem with chance constraints (CAP) and its distributionally robust counterpart DR-CAP. We present a technique for estimating big-M in such a formulation that takes advantage of the ambiguity set. We consider a 0-1 bilinear knapsack set to develop valid inequalities for CAP and DR-CAP. This is generalized to the joint chance constraint problem. A probability cut framework is also developed to solve DR-CAP. A computational study on problem instances obtained from using real hospital surgery data shows that the developed techniques allow us to solve certain model instances and reduce the computational time for others. The use of Wasserstein ambiguity set in the DR-CAP model improves the out-of-sample performance of satisfying the chance constraints more significantly than the one possible by increasing the sample size in the sample average approximation technique. The solution time for DR-CAP model instances is of the same order as that for solving the CAP instances. This finding is important because chance constrained optimization models are very difficult to solve when the coefficients in the constraints are random.