EURO 2025 Leeds
Abstract Submission

1284. A Branch-Price-and-Cut Algorithm for the Kidney Exchange Problem

Invited abstract in session MA-11: Kidney Exchange, stream OR in Healthcare (ORAHS).

Monday, 8:30-10:00
Room: Clarendon SR 1.03

Authors (first author is the speaker)

1. Maxime Ogier
Centrale Lille
2. Claudia Archetti
Università degli Studi di Brescia
3. Diego Cattaruzza
University of Udine
4. Matteo Petris
École nationale des ponts et chaussées
5. Frédéric Semet
CRIStAL, Centrale Lille

Abstract

We study a Kidney Exchange Problem (KEP) with altruistic donors and incompatible patient-donor pairs.
Kidney exchanges can be modelled in a directed graph as circuits starting and ending in an incompatible pair or as paths starting at an altruistic donor.
For medical reasons, circuits and paths are of limited length and are associated with a medical benefit to perform the transplants.
The aim of the KEP is to determine a set of disjoint kidney exchanges of maximal medical benefit or maximal cardinality.

We consider a set packing formulation for the KEP with exponentially-many variables associated with circuits and paths, and develop a Branch-Price-and-Cut algorithm (BPC) to solve it.
We decompose the pricing problem into a subproblem to price out the path variables and several subproblems to price out the circuit variables.
We strengthen the linear relaxation via the inclusion of a family of non-robust inequalities.

We perform extensive computational experiments to assess the performances of the BPC algorithm on three sets of instances from the literature and on a newly generated set of challenging instances.
On the easiest instances, it yields comparable results with the literature, while on the other sets it clearly outperforms the previous results.
Hence, contrary to the existing literature, the BPC algorithm is the only exact approach able to effectively solve various and difficult instances with both objective functions and long chains and cycles.

Keywords

Status: accepted

Back to the list of papers