Jeudi 25 novembre 2021
Chifaa Dahik (Université de Franche-Comté)
Optimisation discrète robuste en présence d’incertitude ellipsoïdale
On s’intéresse à la version robuste des problèmes linéaires à variables binaires avec un ensemble d’incertitude ellipsoïdal 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, nous examinons la puissance d’exploration des itérations internes binaires de la méthode. 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 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. 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.
Finalement, une autre adaptation de l’algorithme de Frank-Wolfe a été réalisé pour le problème du k-médiane, accompagnée d’un algorithme d’arrondissement qui satisfait les contraintes.