KidneyExchange.jl: a Julia package for solving the kidney exchange problem with branch-and-price
- The kidney exchange problem (KEP) is an increasingly important healthcare man-
agement problem in most European and North American countries which consists of
matching incompatible patient-donor pairs in a centralized system. Despite the signif-
icant progress in the exact solution of KEP instances in recent years, larger instances
still pose a challenge especially when non-directed donors are taken into account. In
this article, we present a branch-and-price algorithm for the exact solution of KEP
in the presence of non-directed donors. This algorithm is based on a disaggregated
cycle and chains formulation where subproblems are managed through graph copies.
We additionally present a branch-and-price algorithm based on the position-indexed
chain-edge formulation as well as two compact formulations. We formalize and ana-
lyze the complexity of the resulting pricing problems and identify the conditions under
which they can be solved using polynomial-time algorithms. We propose several algo-
rithmic improvements for the branch-and-price algorithms as well as for the solution
of pricing problems. We extensively test all of our implementations using a bench-
mark made up of different types of instances. Our numerical results show that the
proposed algorithm can be significantly faster compared to the state-of-the-art. All
models and algorithms presented in the paper are gathered in an open-access Julia
package, KidneyExchange.jl.
