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
T2 - 24th International Conference on Logic Programming, ICLP 2008
Y2 - 9 December 2008 through 13 December 2008
ER -