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.
|