Advertisement
Published in:
2008 | OriginalPaper | Chapter
Efficient Algorithms for Functional Constraints
Authors : Yuanlin Zhang, Roland H. C. Yap, Chendong Li, Satyanarayana Marisetti
Published in: Logic Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Functional constraints
are an important constraint class in Constraint Programming (CP) systems, in particular for Constraint Logic Programming (CLP) systems. CP systems with finite domain constraints usually employ CSP-based solvers which use local consistency, e.g. arc consistency. We introduce a new approach which is based instead on
variable substitution
. We obtain efficient algorithms for reducing systems involving functional and
bi-functional constraints
together with other non-functional constraints. It also solves globally any CSP where there exists a variable such that any other variable is reachable from it through a sequence of functional constraints. Our experiments show that variable elimination can significantly improve the efficiency of solving problems with functional constraints.