Arc consistency on n-ary monotonic and linear constraints

Zhang Yuanlin, Roland H.C. Yap

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

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 languageEnglish
Pages (from-to)470-483
Number of pages14
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1894
StatePublished - 2000

Fingerprint Dive into the research topics of 'Arc consistency on n-ary monotonic and linear constraints'. Together they form a unique fingerprint.

Cite this