Des symétries locales de variables aux symétries globales - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

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.
Fichier principal
Vignette du fichier
pages-181-190-article47.pdf (311.29 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00291567 , version 1 (27-06-2008)

Identifiants

  • HAL Id : inria-00291567 , version 1

Citer

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⟩
58 Consultations
107 Téléchargements

Partager

Gmail Facebook X LinkedIn More