A New Branch-and-Price Approach for the Kidney Exchange Problem

Abstract

The kidney exchange problem (KEP) is an optimization problem arising in the framework of transplant programs that allow exchange of kidneys between two or more incompatible patient-donor pairs. In this paper an approach based on a new decomposition model and branch-and-price is proposed to solve large KEP instances. The optimization problem considers, hierarchically, the maximization of the number of transplants and the minimization of the size of exchange cycles. Computational comparison of different variants of branch-and-price for the standard and the proposed objective functions are presented. The results show the efficiency of the proposed approach for solving large instances.