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 metadata

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 : Monday, February 15, 2021 - 10:30:33 AM
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. 8èmes Journées Francophones de Programmation par Contraintes (JFPC 2012), May 2012, Toulouse, France. pp.338-347. ⟨lirmm-00752306⟩

Share

Metrics

Record views

258

Files downloads

391