Title :

A Branch-Price-and-Cut algorithm for the Kidney Exchange Problem

Author(s) :

Petris, Matteo [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Archetti, Claudia [Auteur]
ESSEC Business School
Cattaruzza, Diego [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Ogier, Maxime [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Semet, Frédéric [Auteur]
Integrated Optimization with Complex Structure [INOCS]

Publication date :

2024-02-23

English keyword(s) :

Kidney exchange
altruistic donors
elementary paths
elementary circuits
Branch-Price-and-Cut
Kidney exchange altruistic donors elementary paths elementary circuits Branch-Price-and-Cut

HAL domain(s) :

Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

In this paper, 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 ...
Show more >In this paper, 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 disjointkidney 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. The former can be formulated as an Elementary Longest Path Problem with Length Constraints (ELPPLC), that is NP-hard in the strong sense, and solved by a label correcting dynamic programming algorithm.Conversely, the latter can be formulated as a Longest Path Problem with Length Constraints (LPPLC) and solved in polynomial time.We strengthen the linear relaxation via the inclusion of a family of non-robust inequalities, namely, the subset-row inequalities.We separate them heuristically by looking for violated clique and odd-hole inequalities which are then transformed into subset-row inequalities.We perform extensive computational experiments to assess the performances of the BPC algorithm on three sets of instances from the literature. On the easiest instances, the BPC algorithm yields comparable results with the literature; while on the other two 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.Show less >

Language :

Anglais

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL