Casser les symétries de variables dans un problème "presque" injectif - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2012

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

Abstract

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
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

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

Cite

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⟩
154 View
190 Download

Share

More