(1) Graduate Program in Electrical Engineering
Universidad Autónoma de Nuevo León, Mexico
(2) Graduate Program in Mechanical and Industrial Engineering
University of Toronto, Canada
(3) Graduate Program in Operations Research and Industrial Engineering
The University of Texas at Austin, USA
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 mathematical 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 few years. Several of these models 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 rendering more compact and tractable models to both cycle-only and cycle-and-chain versions. In addition, an efficient algorithm for detecting violated constraints and solving the problem is developed. To assess the value of our enhanced models and algorithm, an extensive computational study was carried out comparing with existing formulations. The results demonstrated the effectiveness of the proposed approach. For example, among the main findings for edge-based cycle-only models, the proposed model (*PRE(i)) uses a new set of constraints and a small subset of the full set of length-k paths that are included in the edge formulation. It was observed that the proposed model achieved a reduction in the number of such paths of more than 98% among all instances tested. With respect to the cycle-and-chain formulations, the proposed model (*ReSPLIT) outperformed Anderson’s arc-based (AA) formulation and the path constrained-TSP formulation on all instances tested. In particular, when tested on the difficult sets of instances from literature], the proposed model (*ReSPLIT) provided the best results when compared to the AA and PC-based models.