New Exact Approaches Tailored for Kidney Exchange Programs with Hierarchical Objectives
Kidney exchange programs increase the rate of living donor kidney transplantation. Whereas effective integer programming models aimed at maximizing the total number of transplants have been proposed in the literature, these cannot always be extended to handle a hierarchy of objectives, which is often a requirement in practice. In “New Algorithms for Hierarchical Optimization in Kidney Exchange Programs,” Delorme, García, Gondzio, Kalcsics, Manlove, and Pettersson introduce a new integer programming framework to solve large-size instances of kidney exchange programs. The authors use an ad hoc preprocessing and a reduced-cost variable fixing algorithm to dramatically decrease the size of the models, and they devise a diving algorithm that exploits the hierarchical structure of the problem to significantly reduce the number of integer programs that need to be solved. They also show that it is possible to transition between models as different layers are traversed in the hierarchy, allowing each layer to be solved with the most effective model. Experiments on three different European kidney exchange programs show that running times can be reduced by up to three orders of magnitude.
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.
Funding:
This work was supported by the Engineering and Physical Sciences Research Council [Grants EP/P028306/1 and EP/P029825/1].
Supplemental Material:
The e-companion is available at
https://doi.org/10.1287/opre.2022.2374
....

New Algorithms for Hierarchical Optimization in Kidney Exchange Programs

10.1287/opre.2022.2374