Skip to Main content Skip to Navigation
Conference papers

Casser les symétries de variables dans un problème "presque" injectif

Résumé : Une des techniques pour éliminer les sym étries de variables est l'ajout de contraintes lexicographiques. Dans le cas g én éral, le nombre de contraintes à ajouter au mod èle pour éliminer toutes les sym étries de variables est potentiellement exponentiel en n le nombre de variables [3]. Dans le cas particulier des problèmes injectifs (avec un AllDiff ), le nombre de contraintes à ajouter est lin éaire en le nombre de variables [8]. En se basant sur la contrainte globale de cardinalité [9], vue comme une g én éralisation de la contrainte All- Di ff, nous caract érisons les probl èmes "presque" injectifs par un param ètre correspondant au nombre de doublons.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00752306
Contributor : Joël Quinqueton <>
Submitted on : Wednesday, June 5, 2013 - 12:14:01 PM
Last modification on : Thursday, July 2, 2020 - 2:19:38 PM
Long-term archiving on: : Friday, September 6, 2013 - 4:08:06 AM

File

paper_35.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00752306, version 1
  • PRODINRA : 316745

Citation

Philippe Vismara, Remi Coletta. Casser les symétries de variables dans un problème "presque" injectif. JFPC'2012 : 8ièmes Journées Françaises de Programmation par Contraintes, May 2012, Toulouse, France. pp.338-347. ⟨lirmm-00752306⟩

Share

Metrics

Record views

233

Files downloads

380