Paper Info
Title
The Ordered Distribute Constraint
Abstract
In this paper we introduce a new cardinality constraint: Ordered Distribute. Given a set of variables, this constraint limits for each value v the number of times v or any value greater than v is taken. It extends the global cardinality constraint, that constrains only the number of times a value v is taken by a set of variables and does not consider at the same time the occurrences of all the values greater than v. We design an algorithm for achieving generalized arc-consistency on Ordered Distribute, with a time complexity linear in the sum of the number of variables and the number of values in the union of their domains. In addition, we give some experiments showing the advantage of this new constraint for problems where values represent levels whose overrunning has to be under control.
Year
DOI
Venue
2010
10.1109/ICTAI.2010.68
International Journal on Artificial Intelligence Tools
Keywords
DocType
Volume
generalized arc-consistency,constraint limit,new constraint,new cardinality constraint,ordered distribute constraint,times v,global cardinality constraint,time complexity,ordered distribute,value v,limiting,constraint programming,computational complexity,algorithm design and analysis,schedules,algorithm,optimization
Conference
20
Issue
ISSN
Citations 
4
1082-3409
2
PageRank 
References 
Authors
0.40
5
2
Name
Order
Citations
PageRank
Thierry Petit1102.71
Jean-charles Régin2131296.59