Efficient algorithms for functional constraints

Yuanlin Zhang, Roland H.C. Yap, Chendong Li, Satyanarayana Marisetti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationLogic Programming - 24th International Conference, ICLP 2008, Proceedings
Pages606-620
Number of pages15
DOIs
StatePublished - 2008
Event24th International Conference on Logic Programming, ICLP 2008 - Udine, Italy
Duration: Dec 9 2008Dec 13 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5366 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on Logic Programming, ICLP 2008
CountryItaly
CityUdine
Period12/9/0812/13/08

Fingerprint Dive into the research topics of 'Efficient algorithms for functional constraints'. Together they form a unique fingerprint.

  • Cite this

    Zhang, Y., Yap, R. H. C., Li, C., & Marisetti, S. (2008). Efficient algorithms for functional constraints. In Logic Programming - 24th International Conference, ICLP 2008, Proceedings (pp. 606-620). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5366 LNCS). https://doi.org/10.1007/978-3-540-89982-2_50