Skip to Main content Skip to Navigation
Conference papers

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

Nicolas Levasseur 1 Patrice Boizumault 1 Samir Loudni 1
1 Equipe CODAG - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

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

File

pages-257-266-article13.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00292657, version 1

Citation

Nicolas Levasseur, Patrice Boizumault, Samir Loudni. Heuristique de choix de valeur dirigée par HQ dans les WCSP. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.257-266. ⟨inria-00292657⟩

Share

Metrics

Record views

224

Files downloads

144