Heuristique de révision et contraintes hétérogènes

Résumé : La plupart des solveurs de contraintes utilisent une méthode de propagation basée sur l'algorithme générique AC-5 [24]. Le principe d'AC-5 est d'abstraire la notion de révision de contrainte. Chaque contrainte dispose d'un propagateur, doté d'un algorithme de propagation spécifique, de complexité et performance variables. Plusieurs travaux ont, par le passé, montré que l'ordre dans lequel les contraintes sont révisées ont un impact non négligeable sur les performances de la propagation [27, 8, 22, 1]. Cependant, la plupart de ces articles se basent sur l'utilisation de propagateurs homogènes, en particulier pour des contraintes binaires définies en extension. Cet article présente différentes idées et techniques permettant un ordonnancement fin des contraintes au sein d'un système de propagation.
Type de document :
Communication dans un congrès
Simon de Givry. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00830360
Contributeur : Ist Inria Saclay <>
Soumis le : mardi 4 juin 2013 - 17:29:22
Dernière modification le : jeudi 22 mars 2018 - 23:26:05
Document(s) archivé(s) le : mardi 4 avril 2017 - 16:54:25

Fichier

paper_7.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00830360, version 1

Collections

Citation

Julien Vion. Heuristique de révision et contraintes hétérogènes. Simon de Givry. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes. 〈hal-00830360〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

140