Manlove David F, McBride Iain, Trimble James
School of Computing Science, University of Glasgow, Sir Alwyn Williams Building, Glasgow, G12 8QQ UK.
Constraints. 2017;22(1):50-72. doi: 10.1007/s10601-016-9249-7. Epub 2016 Aug 11.
The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even in the highly restricted case that each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then present the first Integer Programming (IP) and Constraint Programming (CP) models for min bp hrc. Finally, we discuss an empirical evaluation of these models applied to randomly-generated instances of min bp hrc. We find that on average, the CP model is about 1.15 times faster than the IP model, and when presolving is applied to the CP model, it is on average 8.14 times faster. We further observe that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.
带配偶的医院/住院医师问题（hrc）对有意向的初级医生分配到医院的情况进行建模，其中允许配偶对（通常地理位置相近的）医院对提交联合偏好列表。已知稳定匹配可能不存在，因此我们考虑最小阻塞对数量的hrc问题，即找到一个阻塞对数量最少（即“尽可能稳定”）的匹配的问题。我们证明了这个问题是NP难的，并且即使在每个配偶对只接受一对医院的高度受限情况下也难以近似求解。然而，如果我们进一步假设每个单身住院医师和医院的偏好列表长度最多为2，我们给出了针对这种情况的多项式时间算法。然后，我们提出了用于最小阻塞对数量的hrc问题的第一个整数规划（IP）和约束规划（CP）模型。最后，我们讨论了将这些模型应用于最小阻塞对数量的hrc问题的随机生成实例的实证评估。我们发现，平均而言，CP模型比IP模型快约1.15倍，并且当对CP模型应用预求解时，它平均快8.14倍。我们进一步观察到，对于所考虑的（28,000）个实例，一个解决方案所承认的阻塞对数量非常少，即通常最多为1个，并且从不超过2个。
