Arc Consistency on n-ary Monotonic and Linear Constraints

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(3l C-schema) for enforcing arc consistency on general CSPs isO( ) 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(3 h includes linear inequalities as a special case). Such monotonic constraints can be made arc consistent in time d). The special case of linear inequalities can be made arc consistent in time d) using bounds-consistency which exploits special properties of the projection function