Heuristique de choix de valeur dirigée par HQ dans les WCSP

Résumé : Le formalisme des WCSP [11, 14] (Weighted Constraint Satisfaction Problem) est un cadre général pour modéliser et résoudre des problèmes d'optimisation sous contraintes. 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 mécanismes de filtrage basés sur un calcul de minorants. Dans ces méthodes, les heuristiques de sélection dynamique de variable (MinDom/FutDeg) et de valeur (MinAC) sont parmi les plus efficaces. Dans cet article, nous proposons des nouvelles heuristiques de sélection de valeur basées sur la qualité des solutions (H-Quality). La H-Quality d'une affectation estime sa capacité à être présente dans des solutions de "bonne" qualité. Les expérimentations réalisées avec LDS et DFBB sur des instances réelles (CELAR) et aléatoires montrent que nos heuristiques guident plus efficacement la recherche que MinAC.