Novel integer programming models for the stable kidney exchange problem

• Tipo: Artigo em Revista Científica Internacional
• Data: 2023

Autores

Klimentova, X (Autor) Outra; Biro, P (Autor) Outra; Viana, A (Autor) Outra; Costa, V (Autor) Outra; Joao Pedro Pedroso (Autor) FCUP

Revista

Título: European Journal of Operational Research

Vol. 307

Páginas: 1391-1407

ISSN: 0377-2217

Editora: Elsevier

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Classificação Científica

CORDIS: Ciências Físicas > Matemática > Matemática aplicada > Investigação operacional

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-00T-D4G

DOI: 10.1016/j.ejor.2022.09.031

Abstract (EN): Kidney exchange programs (KEPs) represent an additional possibility of transplant for patients suffering from end-stage kidney disease. If a patient has a willing living donor with whom the patient is not compatible, the pair recipient-donor can join a pool of incompatible pairs and, if compatibility between recipient and donor in two or more pairs exists, organs can be exchanged between them. The problem can be modelled as an integer program that in general aims at finding the pairs that should be selected for transplant such that maximum number of transplants is performed. In this paper, we consider that for each recipient there may exist a preference order over the organs that he/she can receive, since a recipient may be compatible with several donors but the level of compatibility with the recipient might vary for different donors. Under this setting, the aim is to find the maximum cardinality stable exchange, a solution where no blocking cycle exists, i.e., there is no cycle such that all recipients prefer the donor in that cycle rather than that in the exchange. For this purpose we propose four novel integer programming models based on the well-known edge and cycle formulations, and also on the position-indexed formulation. These formulations are adjusted for both finding stable and strongly stable exchanges under strict preferences and for the case when ties in preferences may exist. Further-more, we study a situation when the stability requirement can be relaxed by addressing the trade-off between maximum cardinality versus number of blocking cycles allowed in a solution. The effectiveness of the proposed models is assessed through extensive computational experiments on a wide set of in-stances. Results show that the cycle-edge and position-indexed formulations outperform the other two formulations. Another important practical outcome is that targeting strongly stable solutions has a much higher negative impact on the number of transplants (with an average reduction of up to 20% for the bigger instances), when compared to stable solutions.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 17