Cohérences Locales Paramétrées - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Cohérences Locales Paramétrées

Résumé

Les solveurs de contraintes maintiennent uniformé-ment le même niveau de cohérence locale (généralement la cohérence d'arc) indépendamment de l'instance du problèmeà résoudre. Nous proposons le concept de co-hérence locale paramétrée, une approche originale qui permet d'ajuster le niveau de cohérence locale en fonc-tion de l'instance du problèmeà résoudre et en fonction de la partie du problème dans laquelle s'effectue la propagation. Nous n'utilisons pas comme paramètre l'une des caractéristiques de l'instance, comme le font les por-tefeuilles de solveurs. Nous utilisons comme paramètre la stabilité des valeurs, une caractéristique basée sur l'état de l'algorithme de cohérence d'arc durant son exécution. Les cohérences locales paramétrées appliquentà une valeur, la cohérence d'arc ou un autre niveau de co-hérence plusélevé, selon que la stabilité de cette valeur est en dessus ou en dessous d'un seuil donné. L'approche que nous proposons permet d'obtenir un bon compromis entre la capacité d'une cohérence localeà supprimer des valeurs et le coût en temps pour atteindre ce niveau de cohérence dans un réseau de contraintes. Nous validons notre approche sur différents problèmes de la dernière compétition des solveurs de contraintes.
Fichier principal
Vignette du fichier
balafrej-13_pLC.pdf (416.85 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00830410 , version 1 (10-10-2019)

Identifiants

  • HAL Id : lirmm-00830410 , version 1

Citer

Amine Balafrej, Christian Bessiere, Remi Coletta, El Houssine Bouyakhf. Cohérences Locales Paramétrées. 9èmes Journées Francophones de Programmation par Contraintes (JFPC 2013), Jun 2013, Aix-en-Provence, France. ⟨lirmm-00830410⟩
147 Consultations
44 Téléchargements

Partager

Gmail Facebook X LinkedIn More