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).