Aller au menu Aller au contenu
Optimisation combinatoire
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Optimisation combinatoire
Optimisation combinatoire

> Recherche > Optimisation combinatoire

Soutenance de thèse de Lucie PANSART (OC) le 18 septembre 2020 à 14h00 - Amphi Gosse et visio conférence - Grenoble INP

Publié le 16 septembre 2020
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
Soutenance 18 septembre 2020

Intitulée : " Algorithmes de chemin élémentaire : application aux échanges de reins "

Les membres du jury :
 
  • 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.
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

mise à jour le 25 septembre 2020

Université Grenoble Alpes