Robust Models for the Kidney Exchange Problem
Margarida Carvalho (),
Xenia Klimentova (),
Kristiaan Glorie (),
Ana Viana () and
Miguel Constantino ()
Additional contact information
Margarida Carvalho: CIRRELT and Département d’informatique et de recherche opérationnelle, Université de Montréal, Montreal, Quebec H3T 1J4, Canada
Xenia Klimentova: INESC TEC, Porto 4200-465, Portugal
Kristiaan Glorie: Erasmus Q-Intelligence, 3000 DR Rotterdam, Netherlands
Ana Viana: INESC TEC, Porto 4200-465, Portugal; School of Engineering, Polytechnic of Porto, Porto 4249-015, Portugal
Miguel Constantino: CMAFCIO and Faculdade de Ciências da Universidade de Lisboa, Lisboa 1749-016, Portugal
INFORMS Journal on Computing, 2021, vol. 33, issue 3, 861-881
Abstract:
Kidney exchange programs aim at matching end-stage renal disease patients who have a willing but incompatible kidney donor with another donor. The programs comprise a pool of such incompatible patient-donor pairs and, whenever a donor from one pair is compatible with the patient of another pair, and vice versa, the pairs may be matched and exchange kidneys. This is typically a two-step process in which, first, a set of pairs is matched based on preliminary compatibility tests and, second, the matched pairs are notified and more accurate compatibility tests are performed to verify that actual transplantation can take place. These additional tests may reveal incompatibilities not previously detected. When that happens, the planned exchange will not proceed. Furthermore, pairs may drop out before the transplant, and thus the planned exchange is canceled. In this paper, we study the case in which a new set of pairs may be matched if incompatibilities are discovered or a pair withdraws from the program. The new set should be as close as possible to the initial set in order to minimize the material and emotional costs of the changes. Various recourse policies that determine the admissible second-stage actions are investigated. For each recourse policy, we propose a novel adjustable robust integer programming model. We also propose solution approaches to solve this model exactly. The approaches are validated through thorough computational experiments. Summary of Contribution : In the paper, we present an original work related to the modeling and optimization approaches for Kidney Exchange Programs (KEPs). Currently, KEPs represent an alternative way for patients suffering from renal failure to find a compatible (living) donor. The problem of determining an assignment of patients to (compatible) donors that maximizes the number of transplants in a KEP can be seen as a vertex-disjoint cycle packing problem. Thus, KEPs have been extensively studied in the literature of integer programming. In practice, the assignment determined to a KEP might not be implemented due to withdraws from the program (e.g., a more accurate compatible test shows a new incompatibility or a patient health condition unable him/her to participate on the KEP). In our paper, we model the problem of determining a robust solution to the KEP, i.e., a solution that minimizes the material and emotional costs of changing an assignment. In this way, we propose and design solution approaches for three recourse policies that anticipate withdraws. Through computational experiments we compare the three recourse policies and validate the practical interest of robust solutions.
Keywords: kidney exchange; robust optimization; integer programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)
Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0986 (application/pdf)
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:inm:orijoc:v:33:y:2021:i:3:p:861-881
Access Statistics for this article
More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().