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

Filipe Alvelos (), Xenia Klimentova () and Ana Viana ()
Additional contact information
Filipe Alvelos: Universidade do Minho
Xenia Klimentova: INESC TEC, Campus da FEUP
Ana Viana: INESC TEC, Campus da FEUP

Annals of Operations Research, 2019, vol. 272, issue 1, No 19, 429-444

Abstract: Abstract 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.

Keywords: Kidney exchange problem; Expected number of transplants; Integer programming; Branch-and-price (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2647-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:272:y:2019:i:1:d:10.1007_s10479-017-2647-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2647-4

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().