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.
Domains
Artificial Intelligence [cs.AI]Origin | Files produced by the author(s) |
---|
Loading...