EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1394. Integer linear programming formulations for the kidney exchange problem with reserve arcs

Invited abstract in session TC-10: Kidney Exchange I, stream OR in Health Services (ORAHS).

Tuesday, 12:30-14:00
Room: 11 (building: 116)

Authors (first author is the speaker)

1. Maxence Delorme
Tilburg University
2. Wendy Liu
Tilburg University
3. David Manlove
School of Computing Science, University of Glasgow

Abstract

We are interested in the kidney exchange problem with reserve arcs (KEPRA), an extension of the classical kidney exchange problem in which one is allowed to select arcs that do not appear in the compatibility graph (called reserve arcs, or RA). We study two optimization problems: (i) what is the maximum number of transplants given an upper bound on the total number of RA that can be used, and (ii) what is the minimum number of RA that is necessary for every recipient to receive a kidney.

This problem is motivated by a recent breakthrough in the field of kidney transplant reported by the newspaper “The Guardian” stating that “researchers have successfully altered the blood type of three donor kidneys in a gamechanging discovery that could significantly improve the chances of patients waiting for a transplant finding a match”.

We show that, even though existing integer linear programming (ILP) formulations can easily be extended to the KEPRA, solving these models with a state-of-the-art ILP solver requires a long computation time due to the fact that the compatibility graph is complete. We then show that there always exists an optimal KEPRA solution in which every cycle contains at most one RA, and use that property to develop an effective variable reduction procedure for each model. We finally use that property to extend the well-known position indexed chain-edge formulation to the KEPRA and show that it clearly outperforms all the other ILP models.

Keywords

Status: accepted

Back to the list of papers