Mathematical models for stable matching problems with ties and incomplete lists

We present new integer linear programming (ILP) models for NPhard optimisation problems in instances of the Stable Marriage problem with Ties and Incomplete lists (SMTI) and its many-to-one generalisation, the Hospitals / Residents problem with Ties (HRT). These models can be used to eciently solve these optimisation problems when applied to (i)instances derived from real-world applications, and (ii) larger instancesthat are randomly-generated. In the case of SMTI, we consider instancesarising from the assignment of children to adoptive families, wherepreferences are obtained from a quality measure of each possibleassignment of child to family. In this case we seek a maximum weightstable matching. We present new theory and algorithms for preprocessinginstances of SMTI with ties on both sides, as well as new ILP models.Algorithms based on existing state-of-the-art models only solve 6 of our22 real-world instances within an hour per instance, and our new modelssolve all 22 instances within a mean runtime of 60 seconds. For HRT, weconsider instances derived from the problem of assigning junior doctorsto foundation posts in Scottish hospitals. Here we seek a maximum sizestable matching. We show how to extend our models for SMTI to the HRTcase. For the real instances, we reduce the mean runtime from an averageof 144 seconds when using state-of-the-art methods, to 3 seconds whenusing our new ILP-based algorithms. We also show that our modelsconsiderably outperform state-of-the-art models on larger randomlygeneratedinstances of SMTI and HRT.

我们提出了针对NP难（NP-hard）优化问题的新型整数线性规划（ILP）模型，这些问题存在于带偏好序与不完全列表的稳定婚姻问题（Stable Marriage problem with Ties and Incomplete lists, SMTI）及其多对一泛化形式——带偏好序的医院/居民问题（Hospitals/Residents problem with Ties, HRT）的实例中。这些模型应用于两类实例时可高效求解上述优化问题：（i）源自实际应用的实例；（ii）随机生成的大规模实例。对于SMTI问题，我们考虑的实例来自儿童与收养家庭的匹配场景——其中偏好基于每个儿童-家庭可能匹配的质量度量得出，目标是找到最大权重稳定匹配。我们提出了针对双方均含偏好序的SMTI实例的预处理新理论与算法，以及新型ILP模型。基于现有最先进模型的算法在每实例一小时时限内仅能解决22个实际实例中的6个，而我们的新模型解决全部22个实例的平均运行时间仅为60秒。对于HRT问题，我们考虑的实例源自苏格兰医院中初级医生与基础岗位的匹配场景，目标是找到最大规模稳定匹配。我们展示了如何将SMTI问题的模型扩展至HRT场景。此外，我们还证明，在SMTI与HRT的随机生成大规模实例上，我们的模型显著优于现有最先进模型。