TY - JOUR
T1 - Solving functional constraints by variable substitution
AU - Zhang, Yuanlin
AU - Yap, Roland H.C.
N1 - Funding Information:
We thank Forrest Sheng Bao for helping draw some of the graphs of the experimental data, Chendong Li for helping implement the elimination algorithm and carrying out some experiments in the earlier stage of this research, and Satyanarayana Marisetti for writing the code for generating random functional constraints and the functional elimination ordering. Portions of this work were supported by National University of Singapore, grant No. 252-000-303-112.
PY - 2011/3
Y1 - 2011/3
N2 - Functional constraints and bi-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 Constraint Satisfaction Problem(s)-based solvers which use local consistency, for example, 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 nonfunctional 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 on random problems show that variable elimination can significantly improve the efficiency of solving problems with functional constraints.
AB - Functional constraints and bi-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 Constraint Satisfaction Problem(s)-based solvers which use local consistency, for example, 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 nonfunctional 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 on random problems show that variable elimination can significantly improve the efficiency of solving problems with functional constraints.
KW - Arc consistency
KW - Constraint logic programming
KW - Constraint satisfaction problem
KW - Functional constraints
KW - Variable substitution
UR - http://www.scopus.com/inward/record.url?scp=79960379006&partnerID=8YFLogxK
U2 - 10.1017/S1471068410000591
DO - 10.1017/S1471068410000591
M3 - Article
AN - SCOPUS:79960379006
VL - 11
SP - 297
EP - 322
JO - Theory and Practice of Logic Programming
JF - Theory and Practice of Logic Programming
SN - 1471-0684
IS - 2-3
ER -