Suppression de symétries pour les méthodes rétro-prospectives

Guillaume Richaud 1 Hadrien Cambazard 1 Narendra Jussien 2
2 TASC - Theory, Algorithms and Systems for Constraints
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
Résumé : Les techniques de suppression de symétries développées pour la programmation par contraintes ont pour objectif d'améliorer l'efficacité des méthodes de résolution en réduisant drastiquement la taille de l'espace de recherche. Parall`element, les méthodes de résolution récentes, telles que les méthodes rétro- prospectives, permettent de s'attaquer à des probl`emes de plus en plus grands, que ce soit par la taille des domaines ou le nombre de variables considérées, et dont l'espace de recherche augmente bien sûr lui aussi. Il paraît donc intéressant de faire profiter les méthodes rétro-prospectives des améliorations permises par les techniques de suppression de symétries qui ont cependant été développées pour un cadre plus classique d'exploration. Dans cet article, nous proposons donc un algorithme hybridant une méthode rétro-prospective (decision-repair) et une technique générique de suppression de symétries (SBDS). Nous présentons plu- sieurs approches pour exprimer et traiter efficacement dans ce cadre les contraintes liées à la suppression des symétries. De premiers résultats expérimentaux valident la démarche.
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 [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085791
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 11:05:25
Dernière modification le : mardi 16 janvier 2018 - 14:36:07
Document(s) archivé(s) le : lundi 5 avril 2010 - 21:57:12

Fichier

Identifiants

  • HAL Id : inria-00085791, version 1

Collections

Citation

Guillaume Richaud, Hadrien Cambazard, Narendra Jussien. Suppression de symétries pour les méthodes rétro-prospectives. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085791〉

Partager

Métriques

Consultations de la notice

183

Téléchargements de fichiers

115