Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Vendredi 25 Novembre 2011

Exploitation de la décomposition arborescente dans une méthode recherche locale pour la résolution de problèmes d'optimisation de contraintes

par Mathieu Fontaine (GREYC, Caen)

Dans les méthodes de recherche locale, le choix de voisinages pertinents à explorer est un point essentiel pour un bon parcours de l'espace de recherche. La prise en compte de la structure du problème à résoudre est primordiale lors de la construction de ces voisinages. La décomposition arborescente est une méthode de partitionnement d'un problème en clusters formant un graphe acyclique. Cette structure est exploitée par des méthodes de recherche complète dans le cadre des problèmes d'optimisation sous contraintes.

Dans cet exposé, nous montrons comment exploiter cette décomposition pour construire des voisinages pertinents pour les méthodes de recherche locale à voisinages larges (VNS). Puis, nous proposons un affinement de cette méthode par la prise en compte de la dureté des contraintes. Enfin, des résultats expérimentaux obtenus dans le cadre des problème de satisfaction de contraintes valuées (WCSP) seront présentés afin de montrer la pertinence et l'efficacité de l'approche proposée.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr