Mathematical models and exact algorithms for kidney exchange problems with immunosuppressants

The kidney exchange problem with reserve arcs (KEP-RA) is an extension of the classical kidney exchange problem in which one is allowed to select in the solution a limited number of arcs that do not belong to the compatibility graph. This problem is motivated by recent breakthroughs in the field of kidney
transplantation involving immunosuppressants that have allowed certain donors to give their kidney to an incompatible recipient. After showing that existing integer linear programming formulations for the kidney exchange problem can easily be extended to KEP-RA, we demonstrate that there always exists an optimal KEP-RA solution in which every cycle contains at most one reserve arc, and we use that property to develop effective variable reduction procedures and new ad hoc modelling structures. Empirical experiments show
that trivial model extensions are not able to cope with medium size instances, whereas our enhanced models are able to solve instances with up to a thousand recipient-donor pairs. We also extend our approaches to include non-directed donors. Finally, we evaluate the number of transplants enabled by each reserve arc in various settings and demonstrate that, even though reserve arcs tend to have a diminishing return, there are instances for which this is not the case.