Soutenance de thèse de Lucie PANSART (OC) le 18 septembre 2020 à 14h00 - Amphi Gosse et visio conférence - Grenoble INP
Intitulée : " Algorithmes de chemin élémentaire : application aux échanges de reins "
Les membres du jury :
Le résumé :
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.
- M. François Clautiaux, Professeur à l'Université de Bordeaux : Rapporteur
- M. Louis-Martin Rousseau, Professeur à Polytechnique Montréal : Rapporteur
- M. Maxime Ogier, Maître de Conférences à l'Université de Lille : Examinateur
- Mme Ana Viana, Professeure à INESC TEC, Polytechnic of Porto : Examinatrice
- M. Hadrien Cambazard, Maître de Conférences à Grenoble INP : Directeur de thèse
- M. Nicolas Catusse, Maître de Conférences à Grenoble INP : Co-encadrant
- M. Gautier Stauffer, Professeur à KEDGE Business School : Invité
Le résumé :
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.