IP-MATCH: Integer Programming for Large and Complex Matching Problems

匹配问题是离散的优化问题，涉及一组申请人，他们寻求共同匹配到一组对象。申请人可能对对象的子集有偏好，反之亦然。偏好可以是有序的，即，可以用第一、第二、第三选择等来表达，或红衣主教，即，存在与将申请者分配给对象相关联的实值效用。典型的目标是最大化匹配的大小，即，本研究将探讨三个具直接实际应用的配对问题：肾脏交换、初级医生分配及教师安置。肾脏交换问题是指肾脏病人有一位自愿但不相容的捐赠者，将其捐赠者与另一位类似情况的病人“交换”。我们的目标是找到一个最佳的病人（申请人）和捐赠者（对象）之间的交换，考虑到潜在的供体肾脏的效用给病人。自2007年以来，NHS血液和移植已经运行了国家活体捐献者肾脏共享计划，该计划每个季度都在其数据库中寻找涉及肾脏移植患者和捐献者的最佳交换集。在初级医生编配计划中，拟聘用的初级医生（申请人）会按医生对医院的优先次序，或医院对医生的优先次序，获编配医院职位（对象）。英国基金会计划办公室每年都会实施一项集中计划，在考虑到这些偏好的情况下，形成医生到医院的最佳分配。具有顺序偏好的匹配问题的另一个示例是教师安置，其中，基于教师对他们准备工作的区域的顺序偏好，将有意向的教师（申请者）分配到地理区域（对象）。在英国，Teach First将毕业生安置在英格兰和威尔士低收入社区的学校。在这两个应用程序中，从申请人的职业和劳动力供应的角度来看，优化偏好被视为重要的。这方面的成功提高了参与者的满意度，并最终提高了社会的福祉。在这三个应用程序中，目前用于构建最优匹配的技术不能扩展到更大的问题大小或更复杂的规划限制和最优性标准。这些问题将出现，例如，1）通过欧洲国家之间计划的跨国合作进行肾脏交换; 2）通过夫妇联合申请匹配地理上接近的医院进行初级医生分配; 3）对于教师安置，通过需要加载-根据地区目标平衡学校的教师分配。在这个项目中，我们将开发新的算法来应对新的挑战上面举例说明。由于基本的优化问题在计算上是困难的，因此必须使用复杂的优化技术。此外，由于问题实例可能很大（例如，英国的初级医生分配每年涉及约7，000名申请者），算法必须是可扩展的和高效的，无论是小型实例还是参与者人数为数千人的大型实例，都必须在几秒或几分钟内运行，而不是几小时或几天。该项目将汇集两个国际领先的研究小组，结合格拉斯哥大学计算科学学院的FATA研究小组在解决匹配问题方面的专业知识，以及爱丁堡大学数学学院的ERGO研究小组在解决整数规划问题方面的专业知识，以解决上述大型和复杂的匹配问题。

Matching Problems are discrete optimization problems involving a set of applicants who seek to be collectively matched to a set of objects. Applicants may have preferences over a subset of the objects, and vice versa. Preferences may be ordinal, i.e., expressible in terms of a first, second, third choice etc., or cardinal, i.e., there is a real-valued utility associated with assigning an applicant to an object. Typical goals are to maximize the size of the matching, i.e., number of matched applicant-object pairs, and/or to optimize social welfare according to the given preferences.This project will focus on three specific Matching Problems with direct practical applications: Kidney Exchange, Junior Doctor Allocation and Teacher Placement.The Kidney Exchange problem involves kidney patients who have a willing but incompatible donor "swapping" their donor with that of another patient in a similar position. The objective is to find an optimal set of swaps among patients (the applicants) and donors (the objects), taking into account the utility of a potential donor kidney to a patient. Since 2007, NHS Blood & Transplant have run the National Living Donor Kidney Sharing Schemes, which seeks out optimal sets of swaps involving kidney transplant patients and donors on their database every quarter. As every matched patient may lead to an additional life saved, optimality is an important goal.In Junior Doctor Allocation, intending junior doctors (the applicants) are to be assigned to hospital posts (the objects), on the basis of ordinal preferences of doctors over hospitals and vice versa. The UK Foundation Programme Office annually runs a centralized scheme to form an optimal allocation of doctors to hospitals, taking these preferences into account. Another example of a Matching Problem with ordinal preferences is Teacher Placement in which intending teachers (the applicants) are to be assigned to geographic regions (the objects) on the basis of teachers' ordinal preferences over regions that they are prepared to work in. In the UK, Teach First places graduates in schools serving low-income communities across England and Wales. In both applications, optimizing preferences is seen as important from both the standpoints of applicants' careers and workforce supply. Success in this respect improves participants' satisfaction and ultimately the well-being of society. In each of the three applications, current techniques used to construct optimal matchings are not scalable to larger problem sizes or more complex planning restrictions and optimality criteria. These issues will arise, for example, 1) for Kidney Exchange through the planned transnational collaboration between European countries; 2) for Junior Doctor Allocation through couples applying jointly to be matched to geographically close hospitals; 3) for Teacher Placement through the need to load-balance the allocation of teachers to schools according to regional targets.In this project we will develop novel algorithms to tackle the new challenges exemplified above. Since the underlying optimization problems are computationally hard, sophisticated optimization techniques must be used. Also, since problem instances can be large (e.g., Junior Doctor Allocation in the UK involves around 7,000 applicants annually), the algorithms must be scalable and efficient, running in seconds or minutes rather than hours or days, for both small instances and also for large instances where the number of participants is in the thousands.This project will bring together two internationally-leading research groups in a new collaboration, combining the expertise of the FATA research group at the School of Computing Science, University of Glasgow, in solving Matching Problems, with that of the the ERGO research group at School of Mathematics, University of Edinburgh, in solving integer programming problems, in order to tackle the above large and complex Matching Problems.