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 Mardi 19 Décembre 2006

Une heuristique de sélection de valeur guidée par Impact dans les WCSP

par Nicolas Levasseur (GREYC)

Le formalisme des WCSP (Weighted Constraint Satisfaction Problem) est une extension des Problèmes de Satisfaction de Contraintes (CSP). Il permet de définir des préférences sur les contraintes afin de modéliser et de résoudre des problèmes d'optimisation. Les WCSP sont très souvent résolus par des méthodes arborescentes qu'elles soient complètes (Depth First Branch and Bound) ou partielles (Limited Discrepancy Search) combinées avec des algorithmes de filtrage. Dans ces méthodes, les heuristiques de sélection dynamique de variable (MinDom/FutDeg) et de valeur (MinAC) permettent de guider efficacement la résolution. L'heuristique MinAC se base sur les inconsistances détectées par la phase de filtrage pour ordonner les valeurs. Malheureusement, celle-ci n'arrive pas à départager les meilleurs candidats et est dépendante des inconsistances détectées et non-détectées par la phase de filtrage.

Nous commencerons par effectuer quelques rappels sur les CSP afin d'introduire la notion de WCSP. En se basant sur la notion d'impact permettant de s'affranchir des inconvénients de MinAC, nous proposons une nouvelle heuristique de sélection de valeur. Les résultats expérimentaux montrent que cette nouvelle heuristique améliore nettement MinAC sur les problèmes générés aléatoirement ainsi que sur certains problèmes du CELAR (problème réel d'allocation de fréquence radio).

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