Abstract
Many problems and applications can be naturally modelled and solved using constraints with more than two variables. Such n-ary constraints, in particular, arithmetic constraints are provided by many finite domain constraint programming systems. The best known worst case time complexity of existing algorithms (GAC-schema) for enforcing arc consistency on general CSPs is O(edn) where d is the size of domain, e is the number of constraints and n is the maximum number of variables in a single constraint. We address the question of efficient consistency enforcing for n-ary constraints. An observation here is that even with a restriction of n-ary constraints to linear constraints, arc consistency enforcing is NP-complete. We identify a general class of monotonic n-ary constraints (which includes linear inequalities as a special case). Such monotonic constraints can be made arc consistent in time O(en3d). The special case of linear inequalities can be made arc consistent in time O(en2d) using bounds-consistency which exploits special properties of the projection function.
Original language | English |
---|---|
Pages (from-to) | 470-483 |
Number of pages | 14 |
Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Volume | 1894 |
State | Published - 2000 |