New Algorithms for Hierarchical Optimization in Kidney Exchange Programs

Maxence Delorme (), Sergio García (), Jacek Gondzio (), Jörg Kalcsics (), David Manlove () and William Pettersson ()
Additional contact information
Maxence Delorme: Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands
Sergio García: School of Mathematics, University of Edinburgh, Edinburgh EH8 9YL, United Kingdom
Jacek Gondzio: School of Mathematics, University of Edinburgh, Edinburgh EH8 9YL, United Kingdom
Jörg Kalcsics: School of Mathematics, University of Edinburgh, Edinburgh EH8 9YL, United Kingdom
David Manlove: School of Computing Science, University of Glasgow, Glasgow G12 8QQ, United Kingdom
William Pettersson: School of Computing Science, University of Glasgow, Glasgow G12 8QQ, United Kingdom

Operations Research, 2024, vol. 72, issue 4, 1654-1673

Abstract: Many kidney exchange programs (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 optimizing 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 modeling the UK KEP, where we show that our improvements reduce running times by three orders of magnitude compared with 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.

Keywords: Optimization; kidney exchange program; hierarchical optimization; exact algorithms; objective diving; preprocessing (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2374 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:4:p:1654-1673

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().