A new branch-and-price approach for the kidney exchange problem

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.This work is financed by the ERDF — European Regional Development Fund through the COMPETE Programme (operational programm for competitiveness), by National Funds through the FCT — Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within project “KEP - New models for enhancing the kidney transplantation process. /FCT ref: PTDC/EGEGES/110940/2009”, by the North Portugal Regional Operational Programme (ON.2 O Novo Norte), under the National Strategic Reference Framework (NSRF), through the European Regional Development Fund (ERDF), and by national funds through FCT within project ”NORTE-07-0124-FEDER-000057”, and has also been supported by FCT through projects “SearchCol: Metaheuristic search by column generation” (PTDC/EIAEIA/100645/2008) and PEst-OE/EEI/UI0319/2014.