Chifaa DAHIK : "Optimisation Discrète Robuste En Présence D’incertitude Ellipsoïdale"

Résumé : Cette thèse traite la version robuste des problèmes linéaires à variables binaires avec un ensemble d'incertitude corrélé. Puisque ce problème est NP-difficile, une approche heuristique intitulée DFW et basée sur l'algorithme de Frank-Wolfe est proposée. Dans cette approche, notre intérêt porte sur les solutions des approximations linéaires que l’algorithme exhibe au long des itérations pendant la relaxation de l’espace des contraintes dans l’enveloppe convexe. Pour les problèmes de petites tailles, la méthode est capable de fournir la solution optimale fournie par CPLEX, après quelques centaines d’itérations. De plus, contrairement à la méthode exacte, notre approche s’applique à des problèmes de grandes tailles également. Les résultats numériques ont été appliqués au plus court chemin robuste. Un autre objectif de cette thèse est de proposer une relaxation semi-définie positive (SDP) pour le plus court chemin robuste qui fournit une borne inférieure pour valider des approches telles que l’algorithme DFW. Ceci permet d’éviter la comparaison entre la solution heuristique et celle proposée par la méthode exacte. Le problème relaxé est le résultant d’une bidualisation du problème. Puis le problème relaxé est résolu en utilisant une version creuse d'une méthode de décomposition dans un espace produit. Cette méthode de validation est adaptée aux problèmes de grande taille. Les expériences numériques montrent que l’écart entre les solutions proposées par les méthodes exacte et heuristique est relativement petit. Finalement, une autre adaptation de l'algorithme de Frank-Wolfe a été réalisé pour le problème du k-médiane. Elle consiste d'abord à relaxer les contraintes de binarité et à utiliser l'algorithme de Frank-Wolfe pour le problème convexe. Ensuite, elle utilise une technique d'arrondissement pour la moyenne des solutions intermédiaires de l'algorithme afin de donner une solution heuristique qui est une solution qui satisfait les contraintes de clustering. Les résultats montrent que cette approche donne la solution optimale dans la plupart des cas, et qu'elle donne des solutions proches de l'optimal lorsqu'elles ne le sont pas.

Composition du jury :

M. Jean-Marc NICOD Professeur Université Bourgogne Franche-Comté - Directeur de thèse
M. Landy RABEHASAINA Maître de conférences Université de Franche-Comté - Co-directeur de thèse
Mme Zeina AL MASRY Maître de conférences ENSMM - Co-encadrante de thèse
Mme Andréa Cynthia SANTOS Professeure Université Le Havre - Rapporteure
M. Imed KACEM Professeur Université de Lorraine - Rapporteur
M. Clément DOMBRY Professeur Université de Franche-Comté - Examinateur
M. Stéphane CHRETIEN Professeur Université de Lyon 2 - Examinateur
M. Kim Thang NGUYEN Professeur Université de Paris Saclay - Examinateur

Localisation : Amphithéâtre Jules Haag - ENSMM, 26 Rue de l'Epitaphe - 25000 Besançon