Séminaire de Mathématiques Discrètes, Optimisation et Décision

Olivier Spanjaard (LIP6 - Université de Paris 6)

Algorithmes exacts pour l'optimisation d'opérateurs OWA dans des problèmes d'arbres couvrants multi-objectifs

Cet exposé portera sur la version multi-objectifs du problème de l'arbre couvrant optimal. Plus précisément, nous nous intéresserons à la détermination d'un arbre couvrant optimisant la moyenne ordonnée pondérée (OWA). Nous montrerons tout d'abord que le problème est faiblement NP-difficile. Nous proposerons ensuite différentes formulations en programmation linéaire en variables mixte, selon différentes sous-classes d'opérateurs OWA. En outre, nous présenterons des procédures de prétraitement dont la validité dépendra là aussi de la sous-classe des opérateurs OWA considérés. Ces procédures s'appuient sur des conditions d'optimalité généralisées et sur des bornes calculables efficacement. Leur impact sur les temps de résolution obtenus sera évalué sur la base d'expériences numériques.
 

Retour à la page du séminaire