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.
Type de document :
Communication dans un congrès
Simon de Givry. JFPC'2012 : 8ièmes Journées Françaises de Programmation par Contraintes, May 2012, Toulouse, France. pp.338-347, 2012
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00752306
Contributeur : Joël Quinqueton <>
Soumis le : mercredi 5 juin 2013 - 12:14:01
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : vendredi 6 septembre 2013 - 04:08:06

Fichier

paper_35.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00752306, version 1

Citation

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

Partager

Métriques

Consultations de la notice

181

Téléchargements de fichiers

236