| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
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.
Cited literature [14 references]
https://hal.inria.fr/inria-00292657
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, July 2, 2008 - 11:44:07 AM
Last modification on : Thursday, February 7, 2019 - 5:27:46 PM
Long-term archiving on: : Friday, May 28, 2010 - 9:21:34 PM
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, July 2, 2008 - 11:44:07 AM
Last modification on : Thursday, February 7, 2019 - 5:27:46 PM
Long-term archiving on: : Friday, May 28, 2010 - 9:21:34 PM
File
pages-257-266-article13.pdf
Files produced by the author(s)