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
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. JFPC 2012 - 8es Journées Francophones de Programmation par Contraintes, May 2012, Toulouse, France. pp.338-347. ⟨lirmm-00752306⟩
159 View
191 Download

Share

More