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

匹配问题是离散的优化问题，涉及一组申请者，他们寻求被集体匹配到一组对象。申请者可能对对象的子集具有偏好，反之亦然。偏好可以是序数的，即可以用第一、第二、第三选择等来表达，也可以是基数的，即存在与将申请者分配给对象相关联的实值效用。典型的目标是最大化匹配的规模，即匹配的申请者-对象对的数量，和/或根据给定的偏好来优化社会福利。本项目将集中于三个具有直接实际应用的具体匹配问题：肾脏交换、初级医生分配和教师安置。肾脏交换问题涉及肾脏患者，他们有自愿但不相容的捐赠者将其捐赠者与处于类似位置的另一名患者的捐赠者交换。其目的是在患者(申请者)和捐赠者(对象)之间找到一组最佳的互换，同时考虑到潜在捐赠者肾脏对患者的效用。自2007年以来，NHS血液和移植中心一直在运行全国活体捐赠者肾脏共享计划，该计划每季度在他们的数据库中寻找涉及肾移植患者和捐赠者的最佳交换方案。由于每个匹配的患者都可能导致额外的生命挽救，最优是一个重要的目标。在初级医生分配中，未来的初级医生(申请者)被分配到医院的职位(对象)，根据医生对医院的顺序偏好，反之亦然。英国基金会计划办公室每年都会运行一项集中计划，以形成对医院医生的最佳分配，并考虑到这些偏好。有序偏好匹配问题的另一个例子是教师安置，即根据教师对他们准备工作的地区的有序偏好，将未来的教师(申请者)分配到地理区域(对象)。在英国，Teach First将毕业生安置在为英格兰和威尔士的低收入社区服务的学校。在这两个申请中，从申请者的职业生涯和劳动力供应的角度来看，优化偏好都被视为重要的。这方面的成功提高了参与者的满意度，并最终提高了社会的福祉。在这三个应用中，当前用于构建最优匹配的技术不能扩展到更大的问题规模或更复杂的规划约束和最优标准。这些问题将会出现，例如，1)通过欧洲国家之间计划的跨国合作进行肾脏交换；2)通过夫妇共同申请匹配到地理位置相近的医院来分配初级医生；3)通过需要根据区域目标对教师分配进行负载平衡来实现教师安置。在这个项目中，我们将开发新的算法来应对上述新的挑战。由于潜在的优化问题在计算上是困难的，必须使用复杂的优化技术。此外，由于问题实例可能很大(例如，在英国，初级医生分配每年涉及约7000名申请者)，算法必须是可扩展和高效的，无论是对于小实例还是对于参与人数数以千计的大实例，算法都必须在几秒或几分钟而不是几小时或几天内运行。该项目将在一个新的合作中将两个国际领先的研究小组聚集在一起，将格拉斯哥大学计算科学学院的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.