La contrainte Increasing NValue

Nicolas Beldiceanu 1 Fabien Hermenier 1, 2 Xavier Lorca 1 Thierry Petit 1
2 ASCOLA - Aspect and composition languages
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Résumé : Cet article introduit la contrainte Increasing NValue, qui restreint le nombre de valeurs distinctes affectées à une séquence de variables, de sorte que chaque variable de la séquence soit inférieure ou égale à la variable la succédant immédiatement. Cette contrainte est une spécialisation de la contrainte NValue, motivée par le besoin de casser des symétries. Il est bien connu que propager la contrainte NValue est un problème NP-Difficile. Nous montrons que la spécialisation au cas d'une séquence ordonnée de variables rend le problème polynomial. Nous proposons un algorithme d'arc-consistance ayant une complexité temporelle en O(sum D), où sum D est la somme des tailles des domaines. Cet algorithme est une amélioration significative, en termes de complexité, des algorithmes issus d'une représentation de la contrainte Increasing NValue à l'aide d'automates ou de la contrainte SLIDE. Nous utilisons notre contrainte dans le cadre d'un problème d'allocation de ressources.
Type de document :
Communication dans un congrès
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.61-70, 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00520296
Contributeur : Christophe Lecoutre <>
Soumis le : samedi 25 septembre 2010 - 11:45:57
Dernière modification le : lundi 5 octobre 2015 - 17:01:38
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 05:48:33

Fichier

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

Identifiants

  • HAL Id : inria-00520296, version 2

Citation

Nicolas Beldiceanu, Fabien Hermenier, Xavier Lorca, Thierry Petit. La contrainte Increasing NValue. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.61-70, 2010. 〈inria-00520296v2〉

Partager

Métriques

Consultations de
la notice

420

Téléchargements du document

117