Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291567
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 2:52:51 PM
Last modification on : Thursday, January 11, 2018 - 6:19:28 AM
Long-term archiving on: : Friday, May 28, 2010 - 9:05:37 PM

File

pages-181-190-article47.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291567, version 1

Collections

Citation

Christophe Lecoutre, Sébastien Tabary. Des symétries locales de variables aux symétries globales. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.181-190. ⟨inria-00291567⟩

Share

Metrics

Record views

131

Files downloads

100