Des symétries locales de variables aux symétries globales

Résumé : Dans cet article, nous proposons de détecter automatiquement les symétries de variables pour les instances CSP en calculant au préalable pour chaque contrainte une partition mettant en valeur les variables dites localement symétriques. A partir de cette information qui peut être obtenue en temps polynomial, nous pouvons alors construire un graphe (appelé lsvgraphe) dont les automorphismes correspondent aux symétries de variables (globales). De manière intéressante, notre approche permet de nous abstraire de la représentation (extension, intention, globale) des contraintes, tandis que la taille des lsv-graphes reste linéaire en fonction de la somme des arités des contraintes. Pour éliminer les symétries de variables, une approche classique consiste à poster des contraintes d'ordre lexicographique. Nous proposons ici un nouvel algorithme qui établit GAC sur de telles contraintes. Celui-ci est simple à implanter, adapté aux solveurs génériques tout en étant capable de gérer des variables partagées. Les résultats expérimentaux obtenus montrent la robustesse de cette approche dans son ensemble : appliquée à de nombreuses séries de problèmes, un nombre plus important d'instances sont résolues tandis que le temps observé pour l'identification (et l'exploitation) des symétries est négligeable.
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.181-190, 2008
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-00291567
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 14:52:51
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : vendredi 28 mai 2010 - 21:05:37

Fichier

pages-181-190-article47.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291567, version 1

Collections

Citation

Christophe Lecoutre, Sébastien Tabary. Des symétries locales de variables aux symétries globales. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.181-190, 2008. 〈inria-00291567〉

Partager

Métriques

Consultations de la notice

109

Téléchargements de fichiers

63