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

IP-MATCH：大型复杂匹配问题的整数规划

• 批准号: EP/P028306/1
• 负责人: David Manlove
• 金额: $ 45.01万
• 依托单位: University of Glasgow
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FP028306%2F1
• 关键词: IP; MATCH; Integer; Programming; Large

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.

匹配问题是离散的优化问题，涉及一组寻求集体与一组对象匹配的申请人。申请人可能对对象的子集有偏好，反之亦然。偏好可以是有序的，即以第一，第二，第三选择等或红衣主教的表达，即，与将申请人分配给对象相关的实用性实用程序。典型的目标是最大化匹配的大小，即匹配的申请人对象对数量和/或根据给定的偏好优化社会福利。该项目将集中于三个直接实践应用的特定匹配问题：肾脏交换，初级医生分配和老师的放置。目的是考虑到潜在的供体肾脏对患者的效用，在患者（申请人）和捐助者（物体）之间找到一组最佳的掉期。自2007年以来，NHS Blood＆移植运行了国家活着的供体肾脏共享方案，该方案寻求每个季度涉及肾脏移植患者和捐助者的最佳掉期。由于每位匹配的患者可能会挽救额外的寿命，因此最佳目标是一个重要的目标。在初级医生分配中，原定的初级医生（申请人）将根据医院的序数偏好而分配给医院职位（对象）（对象），反之亦然。英国基金会计划办公室每年运行一项集中计划，以考虑这些偏好的考虑，将医生最佳分配给医院。与有序偏好相匹配的问题的另一个例子是，教师安置，其中有意的教师（申请人）将根据教师对他们准备在英国工作的地区的有序偏好为基础，将其分配给地理区域（对象）。在这两种应用中，从申请人职业和劳动力供应的角度来看，优化偏好都很重要。在这方面的成功改善了参与者的满足感，并最终使社会福祉。在这三个应用程序中的每一个中，用于构建最佳匹配的当前技术无法扩展到更大的问题大小或更复杂的计划限制和最佳标准。这些问题将出现，例如1）通过欧洲国家之间计划的跨国合作进行肾脏交换； 2）通过共同申请的夫妇分配初级医生，以与地理位置关闭医院相匹配； 3）对于教师的安置，需要根据区域目标加载教师向学校的分配。在该项目中，我们将开发新颖的算法来应对上述新的挑战。由于基本优化问题是计算上的硬性问题，因此必须使用复杂的优化技术。另外，由于问题实例可能很大（例如，英国的初级医生分配每年涉及约7,000名申请人），因此，算法必须可扩展和高效，在几秒钟或几分钟内，而不是数小时或几天，而不是小时或几天，对于大型实例，以及大量参与者的数量，这些小组将在千之间进行研究，将两种研究组合在一起，将其融合在一起，以结合新的研究，以结合新的专业，以结合新的研究。格拉斯哥大学计算科学解决匹配问题，与爱丁堡大学数学学院的ERGO研究小组解决了整数编程问题，以解决上述大型且复杂的匹配问题。

项目成果

Pareto optimal matchings of students to courses in the presence of prerequisites

• DOI: 10.1016/j.disopt.2018.04.004
• 发表时间: 2016-03
• 期刊: Discret. Optim.
• 作者: K. Cechlárová;B. Klaus;D. Manlove

Modelling and optimisation in European Kidney Exchange Programmes

• DOI: 10.1016/j.ejor.2019.09.006
• 发表时间: 2021-01-22
• 期刊: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
• 影响因子: 6.4
• 作者: Biro, Peter;van de Klundert, Joris;Viana, Ana
• 通讯作者: Viana, Ana

A 3/2-Approximation Algorithm for the Student-Project Allocation Problem

学生项目分配问题的 3/2 近似算法

• DOI: 10.4230/lipics.sea.2018.8
• 发表时间: 2018
• 期刊: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
• 作者: Frances Cooper

Improved instance generation for kidney exchange programmes

改进了肾脏交换计划的实例生成

• DOI: 10.1016/j.cor.2022.105707
• 发表时间: 2022
• 期刊: Computers & Operations Research
• 影响因子: 4.6
• 作者: Delorme M

Algorithms for New Types of Fair Stable Matchings

新型公平稳定匹配算法

• 发表时间: 2020
• 作者: Cooper F