EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4362. Robust approaches for the Kidney Exchange Problem

Invited abstract in session WC-35: Robust Optimization: Theory and Applications, stream Stochastic, Robust and Distributionally Robust Optimization.

Wednesday, 12:30-14:00
Room: 44 (building: 303A)

Authors (first author is the speaker)

1. Matteo Petris
École nationale des ponts et chaussées
2. Claudia Archetti
Università degli Studi di Brescia
3. Ivana Ljubic
IDS, ESSEC Business School of Paris

Abstract

In the Kidney Exchange Problem (KEP), kidney exchanges can be modelled in a directed weighted graph as circuits starting and ending in an incompatible pair or as paths starting at an altruistic donor.
The weights on the arcs represent the medical benefit which is a measure of the quality of the transplantation.
For medical reasons, circuits and paths are of limited length.
The aim of the KEP is to determine a set of disjoint kidney exchanges of maximal medical benefit or maximal cardinality (all weights equal to one).
In this work, we consider two types of uncertainty in the KEP which stem from the estimation of the medical benefit (weights of the arcs) and from the failure of a transplantation (existence of an arc).
Both uncertainties are modelled via uncertainty sets with constant budget.
The robust approach entails finding the best KEP solution in the worst-case scenario within the uncertainty set.
We modelled the robust counterpart by means of a max-min formulation which is defined on exponentially-many variables associated with the circuits and paths.
We propose two exact approaches to solve it: one based on the result of Bertsimas and Sim and the other on a reformulation to a single-level problem.
In both cases, the core algorithm is based on a Branch-Price-and-Cut approach where the exponentially-many variables are dynamically generated.
The computational experiments prove the efficiency of our approach.

Keywords

Status: accepted

Back to the list of papers