Algorithmic Applications
This web page describes some practical applications that incorporate algorithms developed by members of the Algorithms group at the School of Computing Science, University of Glasgow.
Scottish Foundation Allocation Scheme (NHS Education for Scotland)
The Scottish Foundation Allocation Scheme was the centralised matching scheme that, until recently, allocated medical graduates to two-year Foundation programmes in Scottish hospitals. The scheme took as input the preferences of applicants over programmes, the “scores” of the applicants (based on academic merit and performance in Situational Judgement Tests) which gave rise to a “master list” of applicants (possibly involving ties, and from which the programmes’ preferences were derived), and the number of posts that each programme had. Between 1999-2012, our algorithms were used to construct stable matchings of applicants to programmes based on these preference lists and capacity constraints; the algorithm also tried to match as many applicants as possible.
Reference: R.W. Irving, Matching medical students to pairs of hospitals: a new variation on a well-known theme, in Proceedings of ESA'98, the Sixth Annual European Symposium on Algorithms, Venice Italy, 1998, Lecture Notes in Computer Science, vol. 1461, pp. 381-392, Springer, 1998.
National Living Donor Kidney Sharing Schemes (NHS Blood and Transplant)
The UK Living Kidney Sharing Schemes (UKLKSS) is a matching scheme run by NHS Blood and Transplant and used to find optimal sets of kidney exchanges in the UK. It is run every quarter and has been in existence since 2007. It currently finds optimal solutions involving pairwise and 3-way exchanges and additionally allows altruistic donors to be involved in domino paired donation (DPD) chains. Software developed by us has been used to find an optimal solution at each quarterly run since July 2008. As of August 2017, 718 actual transplants identified by the software have taken place.
Student-Project Allocation (University of Glasgow, School of Computing Science, and various universities in the UK, Ireland, China and Singapore)
Level 4 undergraduate students undertake an individual project as part of their curriculum. Members of staff publicise project proposals, which students then browse. They are asked to rank 5 projects in order of preference. Our matching algorithms then construct an allocation of students to projects that optimises the cardinality of the matching (in other words, the number of students assigned to projects), and then subject to this objective, the algorithms optimise the profile of the matching in a precise sense (the profile of a matching is the number of students assigned to their first, second, third choice etc.) The algorithms can also take into account upper bounds from staff indicating the maximum number of students that they are willing to supervise.
In recent years these algorithms were also used to allocate students at the: University of Glasgow; University of Edinburgh; University of Kent; University of Leeds; University of Electronic Science and Technology of China (China); University of Limerick (Ireland); and the Singapore Institute of Technology (Singapore).
Reference: D.J. Abraham, R.W. Irving and D.F. Manlove, Two algorithms for the Student-Project Allocation problem, Journal of Discrete Algorithms, 5 (1) :73-90, 2007. Postprint.
Virtual Administration and Learning Environment (University of Glasgow, School of Medicine)
Senior undergraduate students in the School of Medicine at the University of Glasgow are required to choose a range of optional courses, each of which has an upper limit on the number of students that can take that course. Students form preference lists over the elective courses that they are interested in, which they upload via the VALE portal. These lists, together with the course capacities, are then passed as input to our optimal matching algorithms which construct allocations of students to courses. As in the case of student-project allocation above, the primary objective is to maximise the cardinality of the matching (i.e., the number of students who are allocated to an acceptable course). Subject to this condition, the profile of the matching is then optimised. These algorithms are also utilised in the School of Medicine in other contexts, for example in the assignment of medical students to short-term hospital placements, again based on their preference lists over the available posts.
Reference: R.W. Irving, T. Kavitha, K. Mehlhorn, D. Michail and K. Paluch, Rank-maximal matchings, ACM Transactions on Algorithms, 2 : 602-610, 2006.
More information about these and other practical matching schemes can be found here.