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.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.257-266, 2008
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00292657
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 2 juillet 2008 - 11:44:07
Dernière modification le : mardi 5 juin 2018 - 10:14:40
Document(s) archivé(s) le : vendredi 28 mai 2010 - 21:21:34

Fichier

pages-257-266-article13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00292657, version 1

Collections

JFPC08 | GREYC | GREYC-CODAG | COMUE-NORMANDIE

Citation

Nicolas Levasseur, Patrice Boizumault, Samir Loudni. Heuristique de choix de valeur dirigée par HQ dans les WCSP. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.257-266, 2008. 〈inria-00292657〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

179

Téléchargements de fichiers

91

Contact


archive-ouverte@inria.fr