Kidney exchange programmes (KEPs) across the world help match donors and recipients to identify kidney transplantations. Almost all KEPs use a hierarchical set of objectives to determine an optimal set of transplants to perform, and integer linear programming is often used to find such optimal matchings. In this work, we identify the barriers in existing mathematical models and we propose innovative techniques to remove these barriers, vastly reducing solution times and allowing us to significantly increase the potential size of KEPs. Our techniques include two methods to avoid unnecessary variables, as well as a diving algorithm that reduces the need to solve multiple complex integer linear programming models while still guaranteeing the optimality of a final solution. We also show that it is possible to transition between two distinct existing formulations (namely the cycle formulation and the position-indexed chain-edge formulation) between the optimisation of two successive objective functions. We use this technique to devise a new algorithm which, among other features, intelligently exploits the different advantages of the prior two models. We demonstrate the performance of our new algorithms with extensive computational experiments modelling the UK KEP, where we show that our improvements reduce running times by three orders of magnitude compared to the cycle formulation. We also provide substantial empirical evidence that the new methodology offers equally spectacular improvements when applied to modelling the objectives used by Spain and the Netherlands, suggesting that our approach is not just viable, but a significant performance improvement, for many different KEPs across the globe.
Citation
Research report ERGO-20-005, The University of Edinburgh, 2020 (submitted for publication)
Article
View New algorithms for hierarchical optimisation in kidney exchange programmes