Recourse in Kidney Exchange Programs

Bart Smeulders (), Valentin Bartier (), Yves Crama () and Frits C. R. Spieksma ()
Additional contact information
Bart Smeulders: Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven 5612 AE, Netherlands
Valentin Bartier: G-SCOP, Grenoble INP Université Grenoble Alpes, Grenoble 38031, France
Yves Crama: HEC Management School, University of Liège, Liege 4000, Belgium
Frits C. R. Spieksma: Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven 5612 AE, Netherlands

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 1191-1206

Abstract: We introduce the problem of selecting patient-donor pairs in a kidney exchange program to undergo a crossmatch test, and we model this selection problem as a two-stage stochastic integer programming problem. The optimal solutions of this new formulation yield a larger expected number of realized transplants than previous approaches based on internal recourse or subset recourse. We settle the computational complexity of the selection problem by showing that it remains NP-hard even for maximum cycle length equal to two. Furthermore, we investigate to what extent different algorithmic approaches, including one based on Benders decomposition, are able to solve instances of the model. We empirically investigate the computational efficiency of this approach by solving randomly generated instances and study the corresponding running times as a function of maximum cycle length, and of the presence of nondirected donors. Summary of Contribution: This paper deals with an important and very complex issue linked to the optimization of transplant matchings in kidney exchange programs, namely, the inherent uncertainty in the assessment of compatibility between donors and recipients of transplants. Although this issue has previously received some attention in the optimization literature, most attempts to date have focused on applying recourse to solutions selected within restricted spaces. The present paper explicitly formulates the maximization of the expected number of transplants as a two-stage stochastic integer programming problem. The formulation turns out to be computationally difficulty, both from a theoretical and from a numerical perspective. Different algorithmic approaches are proposed and tested experimentally for its solution. The quality of the kidney exchanges produced by these algorithms compares favorably with that of earlier models.

Keywords: Benders decomposition; stochastic programming; kidney exchange; healthcare (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1099 (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:34:y:2022:i:2:p:1191-1206

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 ().