Étude de la dominance dans les CSPs à contraintes de différence

Résumé : La détection dynamique et l'élimination des valeurs symétriques dans les CSPs quelconques est en générale une tâche difficile, mais dans le cas des CSPs à contraintes de différence (NECSPs) , les conditions de symétrie peuvent être simplifiées. Dans cet article, nous étendons le principe de la symétrie à la dominance dans le cas des CSPs à contraintes de différence et nous montrons comment les valeurs dominées sont détectées et éliminées efficacement à chaque noeuds de l'arbre de recherche. Nous proposons un algorithme de détection de valeurs dominées de complexité linéaire. Nous avons implémenté cet algorithme dans un Forward Checking adapté au cas des CSPs à contraintes de différence. Nous avons comparé cette méthode à la méthode DSATUR sur deux classes de problèmes de coloration de graphes : les aléatoires ainsi que sur des instances issues du challenge de DIMACS. Les résultats montrent que notre méthode est en générale la plus performante.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00085783
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 10:23:53
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:08:26

Fichier

Identifiants

  • HAL Id : inria-00085783, version 1

Collections

Citation

Belaïd Benhamou, Mohamed Saïdi. Étude de la dominance dans les CSPs à contraintes de différence. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085783〉

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

122