New algorithms for hierarchical optimisation in kidney exchange programmes

Maxence Delorme, Sergio Garcia, Jacek Gondzio, Jӧrg Kalcsics, David Manlove, William Pettersson

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Many kidney exchange programmes (KEPs) use integer linear programming (ILP) based on a hierarchical set of objectives to determine optimal sets of transplants. We propose innovative techniques to remove barriers in existing mathematical models, vastly reducing solution times and allowing significant increases in potential KEP pool sizes. Our techniques include two methods to avoid unnecessary variables, and a diving algorithm that reduces the need to solve multiple complex ILP models while still guaranteeing optimality of a final solution. We also show how to transition between two existing formulations (namely the cycle formulation and the position-indexed chain-edge formulation) when optimising 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 the Spanish and Dutch KEP objectives, suggesting that our approach is not just viable, but a significant performance improvement, for many KEPs worldwide.
Original languageEnglish
JournalMathematics of Operations Research
Publication statusAccepted/In press - 21 Aug 2022


Dive into the research topics of 'New algorithms for hierarchical optimisation in kidney exchange programmes'. Together they form a unique fingerprint.

Cite this