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 -