Maximizing the expected number of transplants in kidney exchange programs with branch-and-price

In this paper, we propose a branch-and-price approach for solving the problem of maximizing the expected number of transplants in Kidney Exchange Programs (KEPs). In these programs, the decision on which transplants will be conducted is usually made with the support of optimization models with the assumption that all operations will take place. However, after a plan of transplants is defined, a pair may leave the KEP or a more accurate compatibility evaluation exam may invalidate a transplant. To model these possible events we consider probabilities of failure of vertices and of arcs and the objective of maximizing the expected number of transplants. The proposed approach is based on the so-called cycle formulation, where decision variables are associated with cycles. Built on the concept of type of cycle a branch-and-price algorithm is conceived. One subproblem is defined for each type of cycle. We present computational results of the proposed branch-and-price algorithm and compare them with solving directly the cycle formulation (with a general purpose mixed integer programming solver—CPLEX) showing that the proposed approach is the only one suitable for larger instances.This work is financed by the ERDF—European Regional Development Fund through the Operational, Programme for Competitiveness and Internationalization—COMPETE 2020, Programme and by National Funds through the Portuguese funding agency, FCT—Fundação para a Ciência e a Tecnologia within project “mKEP—Models and optimization algorithms for multi-country kidney exchange programs” (POCI-01-0145-FEDER-016677), is also financed by COMPETE: POCI-01-0145-FEDER-007043 and FCT within the Project Scope: UID/CEC/00319/2013 and FCT Project SFRH/BPD/101134/2014.