Mathematical Models and Exact Algorithms for Kidney Exchange Problems with Immunosuppressants

Kidney exchange problems with immunosuppressants extend the classical kidney exchange problem by allowing a limited number of arcs that do not belong to the compatibility graph to be included in the solution. Among these, the kidney exchange problem with reserve arcs (KEP-RA) assumes that any arc can be made compatible, whereas the kidney exchange problem with half-compatible arcs (KEP-HCA) assumes that this is the case only for a subset of arcs. Starting with KEP-RA, we first show that existing integer linear programming formulations for the kidney exchange problem can easily be extended to include reserve arcs. We then demonstrate that there always exists an optimal KEP-RA solution in which every cyclic set of exchanges contains at most one reserve arc, and we use this property to develop effective variable reduction procedures and new ad hoc modeling structures. We also extend these findings to the case where nondirected donors are included. Experiments show that trivial model extensions are not able to cope with medium-sized instances, whereas our enhanced models can solve instances with up to a thousand recipient-donor pairs. We also evaluate the number of transplants enabled by each reserve arc in various settings, demonstrating that although reserve arcs tend to have a diminishing return, there are instances for which this is not the case. Finally, we demonstrate how our techniques can be integrated into a variable and constraint generation algorithm to solve KEP-HCA and show that its performance complements that of a trivial model extension.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: D. Manlove was supported by the Engineering and Physical Sciences Research Council [Grant EP/X013618/1]. This work used the Dutch national e-infrastructure with the support of the SURF Cooperative [Grants EINF-8220 and EINF-12272].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1071) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.1071). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.