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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00520296
Contributor : Christophe Lecoutre <>
Submitted on : Saturday, September 25, 2010 - 11:45:57 AM
Last modification on : Friday, June 22, 2018 - 9:28:44 AM
Long-term archiving on : Friday, December 2, 2016 - 5:48:33 AM

File

beldiceanu.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00520296v2⟩

Share

Metrics

Record views

484

Files downloads

159