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

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.

This project addresses three important societal problems that have a direct impact on human health and well-being: (i) how to increase living kidney donation in the UK; (ii) how to assign teachers participating in Teach First to UK regions in an optimal way; and (iii) how to allocate junior doctors to foundation programmes in UK hospitals optimally.

Kidney transplants are life-saving interventions that also release patients from costly and life-restricting dialysis treatment. An optimal placement of teachers to schools will reduce drop-out rates and help to ensure that the UK can successfully recruit the next generation of motivated teachers. An optimal allocation of junior doctors to hospitals positively influences their future career and job satisfaction and also allows hospitals to meet their workforce requirements.

Considering kidney transplants, patients with a willing but incompatible donor can 'swap' their donor with that of another patient in a similar position through 'cycles'. Altruistic donors can also trigger 'chains', benefiting multiple patients, each of whose willing but incompatible donor donates to the next patient in the chain. NHS Blood and Transplant (NHSBT) run a matching scheme that finds optimal sets of cycles and chains every quarter.

Currently cycles and chains are restricted in size due to logistical reasons. NHSBT are considering allowing longer cycles and chains, which would greatly increase the complexity of the optimization problem. Also there are moves towards transnational collaboration in a European context as envisioned by the ENCKEP COST Action ("European Network for Collaboration on Kidney Exchange Programmes"). Such collaboration involves sharing of donor-patient pools, and whilst it would bring undoubted benefits to the UK (in terms of increased transplants), larger pools also give rise to major optimization challenges.

As part of this project we will develop new algorithms for NHSBT (a Project Partner) that can handle larger datasets, and longer cycles and chains. These algorithms will directly benefit kidney patients by identifying more transplants than before, and will benefit the NHS through financial savings made as a consequence of patients being released from dialysis.

Turning to teacher placement, the particular challenges that this project aims to address are: (i) ensuring that regional targets can be met, meaning that schools in low-income communities succeed in recruiting adequate numbers of teachers, and (ii) optimizing the satisfaction of the applicants in relation to their assigned region; in the past dissatisfaction with the geographic location of their assigned school has been a major factor in applicants dropping out before completing their teaching placement.

The new collaboration with Teach First (a Project Partner) provides an immediate route to realising the impact of improved algorithms for allocating teachers to regions. The benefits that this research would bring about are therefore (i) financial savings for Teach First due to automation of the matching process, (ii) increased quality of life for applicants, and consequently retention problems for schools being alleviated, and (iii) workforce requirements in regions being met.

Regarding the third application, namely junior doctor placement, the UK Foundation Programme Office (UKFPO) runs a matching scheme for allocating junior doctors to foundation programmes in UK hospitals. However the current algorithm can produce matchings that are sub-optimal in various ways.

We will design optimal algorithms that scale up to datasets for junior doctor allocation in a UK-wide setting; current algorithms (based on our prior work in a Scottish context) can only handle datasets that are a tenth of the size of the UK application. Replacing the current UKFPO algorithm with an optimal one will give similar benefits for doctors and hospitals as detailed above for teachers and regions under teacher placement.