Casser les symétries de variables dans un problème "presque" injectif - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement
Communication Dans Un Congrès Année : 2012

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.
Fichier principal
Vignette du fichier
paper_35.pdf (137.33 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00752306 , version 1 (05-06-2013)

Identifiants

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

Citer

Philippe Vismara, Remi Coletta. Casser les symétries de variables dans un problème "presque" injectif. JFPC 2012 - 8es Journées Francophones de Programmation par Contraintes, May 2012, Toulouse, France. pp.338-347. ⟨lirmm-00752306⟩
163 Consultations
195 Téléchargements

Partager

More