Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique

In the Kidney Exchange Problem (KEP), we consider a pool of altruistic donors and incompatible patient-donor pairs. 

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 measures the quality of the associated transplantation.

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 (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 the arcs).

Both uncertainty 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 counter-part by means of a max-min formulation which is defined on exponentially-many variables associated with the circuits and paths.

We propose different exact approaches to solve it: either based on the result of Bertsimas and Sim or 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.