New Formulations and Algorithms for the Kidney Exchange Problem

Abstract: Kidney-paired donation programs assist patients in need of a kidney to swap their incompatible donor with another incompatible patient-donor pair for a suitable kidney in return. The Kidney Exchange Problem (KEP) is a combinatorial optimization problem that consists of finding the maximum set of matches in a directed graph representing the pool of incompatible pairs. Depending on the specific framework, these matches can come in the form of (bounded) directed cycles or directed paths. This gives rise to a family of KEP models that have been studied over the past dozen years. Several require an exponential number of constraints to eliminate cycles and chains that exceed a given length. In this paper, we present enhancements to a subset of existing models that exploit the connectivity properties of the underlying graphs. The first is based on the cycleonly version of the KEP and the second is based on the cycle-and-chain version. An efficient algorithm for detecting violated constraints is developed.

To assess the value of our enhanced models, an extensive computational study was performed in which they were compared with existing formulations. The first observation is that the proposed cyclic-version of the KEP is able to quickly solve instances of realistic size for low to medium density graphs, outperforming the classical edge formulation. It was also observed that our second model proved superior to the existing cycle-and-chain formulations in two out of the three comparisons, and is competitive with the best approaches to date.