Improved instance generation for kidney exchange programmes

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Kidney exchange programmes increase the rate of living donor kidney transplants, and operations research techniques are vital to such programmes. These techniques, as well as changes to policy regarding kidney exchange programmes, are often tested using random instances created by a Saidman generator. We show that instances generated by such a generator differ from real-world instances across a number of important parameters, including the average number of recipients that are compatible with a certain donor. We exploit these differences to devise powerful upper and lower bounds and we demonstrate their effectiveness by optimally solving a benchmark set of Saidman instances in seconds; this set could not be solved in under thirty minutes with previous algorithms. We then present new techniques for generating random kidney exchange instances that are far more similar to real-world instances from the UK kidney exchange programme. This new process for generating random instances provides a more accurate base for comparisons of algorithms and models, and gives policy-makers a better understanding of potential changes to policy leading to an improved
decision-making process.
Original languageEnglish
Article number105707
JournalComputers and Operations Research
Early online date21 Jan 2022
Publication statusPublished - 31 May 2022


Dive into the research topics of 'Improved instance generation for kidney exchange programmes'. Together they form a unique fingerprint.

Cite this