EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1184. A survey on ILP formulations for the kidney exchange problem

Invited abstract in session TC-25: Graph and network optimization, stream Combinatorial Optimization.

Tuesday, 12:30-14:00
Room: 011 (building: 208)

Authors (first author is the speaker)

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

Abstract

Kidney exchange programs facilitate life-saving transplants by allowing patients with willing but incompatible donors to exchange their donors either through cycles, or through chains initiated by non-directed donors. In each matching run, one must identify a maximum weight packing of cardinality-constrained vertex-disjoint cycles and chains on a compatibility graph. This computational problem, known as the Kidney Exchange Problem (KEP), is both theoretically and empirically hard.

We conduct a survey of existing integer linear programming formulations and associated model-related enhancements for the KEP, extending upon prior work by including the most recent advances. Our key contribution lies in addressing a gap in the literature: whereas models for only cycles have been extensively studied, models for both cycles and chains have received less attention. We demonstrate that all cycle models can be adapted to model chains, thereby enabling a comprehensive approach to modelling cycles and chains by merging any cycle model with any chain model. Furthermore, we explore alternative strategies, such as modelling cycles and chains concurrently using a shared set of variables.

Additionally, we conduct extensive computational experiments on generated instances to evaluate and compare the performance of the different model combinations for varying instance parameters, providing valuable insights for practitioners and researchers alike in effectively addressing the KEP.

Keywords

Status: accepted

Back to the list of papers