TY - GEN

T1 - Efficient algorithms for functional constraints

AU - Zhang, Yuanlin

AU - Yap, Roland H.C.

AU - Li, Chendong

AU - Marisetti, Satyanarayana

N1 - Funding Information:
Part of this work was supported by National Univ. of Singapore, grant 252-000- 303-112.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=58549104969&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-89982-2_50

DO - 10.1007/978-3-540-89982-2_50

M3 - Conference contribution

AN - SCOPUS:58549104969

SN - 3540899812

SN - 9783540899815

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 606

EP - 620

BT - Logic Programming - 24th International Conference, ICLP 2008, Proceedings

Y2 - 9 December 2008 through 13 December 2008

ER -