UFC
CNRS


Accueil > Activités > Séminaires > Séminaire doctorant

Séminaires doctorant

par Rougnant Marine - publié le , mis à jour le

Plan d’accès

Le prochain séminaire doctorant aura lieu le jeudi 25 novembre 2021 à 16h30 en présentiel en salle 316B.

Responsables :
Mehdi Dagdoug, Valentin Petit

Exposé à venir

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.

Archives


Archives 2021/2022

Archives 2020/2021

Archives 2019/2020

Archives 2018/2019

Archives 2017/2018

Archives 2016/2017

Journée des Jeunes Chercheurs : Archives

Agenda

iCal