Thèse Lucie PANSART

Auteur : Lucie PANSART
Directeur de thèse : Hadrien CAMBAZARD
Co-encadrant : Nicolas CATUSSE 
Date de soutenance ; 18 septembre 2020
 

Algorithmes de chemin élémentaire :
application aux échanges de reins Algorithms for elementary path problem :
application to kidney exchange

 

Cette thèse traite de problèmes de chemins élémentaires et leur application au problème d’échange de reins. Nous nous concentrons sur des programmes d’échange de reins qui incluent des donneurs altruistes, qui sont essentiels pour les patients avec une maladie rénale, mais représentent un défi pour les méthodes de recherche opérationnelle. Notre objectif est de développer un algorithme efficace qui pourra être utilisé pour résoudre des instances futures, qui sont susceptibles d’impliquer un grand nombre de participants. Nous rencontrons des problèmes étroitement lié au notre : problèmes de packing, de tournée de véhicules, de stable. Pour ce dernier, nous présentons une nouvelle formulation étendue et prouvons qu’elle est idéale et compacte pour les graphes parfaits sans griffe. Nous nous focalisons ensuite sur la conception d’une génération de colonnes dédiée au problème d’échange de reins et nous attaquons à son problème de pricing, NP-difficile. Nous abordons le problème du chemin élémentaire minimum avec contrainte de taille, qui modélise la recherche de chaînes de dons intéressantes à ajouter dans la phase du pricing. Nous étudions des approches dynamiques, en particulier la relaxation NG-route et l’heuristique de color coding, et les améliorons en exploitant la contrainte de taille et la faible densité des graphes considérés. Nous nous intéressons ensuite au color coding dans un contexte plus général, proposant de nouvelles stratégies randomisées qui apportent une garantie d’amélioration. Ces stratégies s’appuient

sur un ordonnancement du graphe et introduisent un biais dans la loi de probabilité pour augmenter les chances de trouver une solution optimale.