Using Optimisation Techniques on the Kidney Exchange Problem

Molly Wilson


Supervised by Richard Booth; Moderated by Bailin Deng

In the Optimal Matching Problem we assumes we have 2 kinds of object, call them As and Bs, and that we have to match each A with a B, and vice versa. Additionally the As have preferences over which Bs they'd like to be matched with, and vice versa. The aim is to output a matching that makes everyone as happy as possible. This problem has many real world applications (e.g., As are newly qualified doctors, Bs are hospitals with open positions), and has several variants, some of which are known to be computationally hard. The aims of this project would be to (i) study the problem , (ii) implement algorithms that can solve it, or that can, at least, find a good approximation to the optimal solution, and (iii) conduct experimental analysis of these algorithms using some available real-world datasets.

Initial Plan (08/02/2021) [Zip Archive]

Final Report (14/05/2021) [Zip Archive]

Publication Form