Skip to Main content Skip to Navigation
Conference papers

Elimination des symétries dans les problèmes injectifs

Résumé : L'ajout de contraintes est utilisé depuis longtemps pour éliminer les symétries dans les CSP. Par exemple, on peut enlever toutes les symétries dans le problème du 'pigeon hole'' en ordonnant les variables. Nous avons généralisé ce résultat à tous les problèmes injectifs, c'est-à-dire où les variables doivent prendre des valeurs toutes distinctes. Dans ce cas il est possible d'éliminer toutes les symétries avec un ordre partiel sur les variables. Nous montrons comment automatiquement calculer un tel ordre en utilisant des algorithmes sur les groupes finis. Nous montrons également que cet ordre partiel peut être combiné avec une méthode éliminant les symétries de valeurs. Des expériences variées montrent l'intérêt pratique de notre méthode.
Complete list of metadata

https://hal.inria.fr/inria-00000092
Contributor : Christine Solnon <>
Submitted on : Friday, May 27, 2005 - 8:59:35 AM
Last modification on : Wednesday, April 11, 2018 - 11:56:05 AM
Long-term archiving on: : Thursday, April 1, 2010 - 9:35:00 PM

Files

Identifiers

  • HAL Id : inria-00000092, version 1

Collections

Citation

Jean-François Puget. Elimination des symétries dans les problèmes injectifs. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.259-266. ⟨inria-00000092⟩

Share

Metrics

Record views

129

Files downloads

112