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

Thumbnail Image
Date
2014
Authors
Xenia Klimentova
Alvelos,F
Ana Viana
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Citation