EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1468. Half-Cycle: A new formulation for modelling kidney exchange problems

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

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

Authors (first author is the speaker)

1. David Manlove
School of Computing Science, University of Glasgow
2. Mathijs Barkel
Department of Econometrics and Operations Research, Tilburg University
3. Maxence Delorme
University of Bologna
4. William Pettersson
University of Glasgow
5. Tom Smeets
Tilburg University

Abstract

A patient who requires a kidney transplant, and who has a willing but incompatible donor, may be able to 'swap' their donor with that of another patient, who is in a similar situation, in a cyclic fashion. Also, non-directed donors can trigger 'chains' of transplants involving multiple donor-recipient pairs. In this talk we introduce the Half-Cycle Formulation (HCF), an integer programming (IP) model for finding optimal sets of exchanges involving cycles and chains among incompatible donor-recipient pairs. In HCF, a cycle (i.e., set of kidney swaps) is represented by two compatible halves, and we also demonstrate how the model can be extended to incorporate chains. After giving several algorithmic enhancements for HCF, we show through computational experiments with an IP solver that our model is competitive in relation to other formulations for certain cycle and chain size limits.

Keywords

Status: accepted

Back to the list of papers