La ROADEF
La R.O.A.D
Evénements
Prix
Publications
Plus
Forums
Connexion
Livre blanc

Annonce d'une soutenance de th

Forum 'Annonces' - Sujet créé le 2005-05-11 par Christian Artigues

Mireille Palpant soutiendra sa thèse préparée au LIA (FRE 2487) dans la spécialité Informatique, intitulée :

Recherche exacte et approchée en optimisation combinatoire : schémas d'intégration et applications.

le vendredi 20 mai 2005 à 14h00 à l'IUP Génie Mathématique et Informatique de l'Université d'Avignon (Amphi Ada Lovelace).

devant le jury composé de

Van Dat Cung, rapporteur
Thierry Mautor, rapporteur
Abderrahim Benslimane, examinateur
Francis Sourd, examinateur
Michel Vasquez, examinateur
Philippe Michelon, directeur de thèse
Christian Artigues, codirecteur de thèse

Vous êtes cordialement conviés à assister à la soutenance et au
pot qui suivra !

---------------------
Résumé :
Le travail présenté dans ce mémoire est focalisé sur la résolution de problèmes d'optimisation combinatoire hautement difficiles par le biais de méthodes incomplètes intégrant des paradigmes issus de deux approches complémentaires, à savoir recherche exacte et approchée. L'intérêt d'une telle coopération est de tirer parti des avantages complémentaires que peuvent apporter l'un et l'autre des composants : optimalité et déterminisme de la composante exacte, rapidité et côté moins systématique de la composante heuristique.
A cet effet, deux méthodologies distinctes ont été abordées : d'une part l'intégration d'une procédure exaustive au sein d'une méthode de recherche de grands voisinages appelée LSSPER (Local Search (with) Sub-Problem Exact Resolution), d'une autre, l'utilisation d'un critère heuristique discrimant pour réduire la taille de l'espace de recherche exploré par une méthode complète dérivée de Resolution Search [Chvatal97].
Pour chacune de ces approches, une validation expérimentale a été réalisée sur divers problèmes académiques ou applicatifs (ordonnancement de projet sous contraintes de ressources, affectation de fréquences, coloration de graphes). Les résultats obtenus, s'ils ne sont pas toujours à la hauteur des meilleurs résultats pouvant être recensés dans la littérature, semblent à tout le moins exhiber l'intérêt de telles méthodologies et laissent entrevoir des perspectives de recherche aussi diverses que prometteuses.