Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T01:07:02.067Z Has data issue: false hasContentIssue false
  • English
  • Français

Solving functional constraints by variable substitution

Published online by Cambridge University Press:  04 February 2011

YUANLIN ZHANG  and
ROLAND H. C. YAP
YUANLIN ZHANG
Affiliation:
Department of Computer Science, Texas Tech University, Lubbock, TX 79409-3104, USA (e-mail: [email protected])
ROLAND H. C. YAP
Affiliation:
School of Computing, National University of Singapore, 13 Computing Drive, 117417, Singapore (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Keywords

Constraint logic programmingConstraint satisfaction problemFunctional constraintsVariable substitutionArc consistency
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 2-3: The 24th International Conference on Logic Programming (ICLP 2008) , March 2011 , pp. 297 - 322
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Affane, M. S. and Bennaceur, H. 1996. A labelling arc consistency method for functional constraints. In Proceedings of the Second International Conference on Principles and Practice of Constraint Programming. Springer, Cambridge, Massachusetts, 16–30.Google Scholar
Bessiere, C., Regin, J., Yap, R. H. C. and Zhang, Y. 2005. An optimal coarse-grained arc consistency algorithm. Artificial Intelligence 165, 2, 165–185.CrossRefGoogle Scholar
Burg, J., Stuckey, P. J., Tai, J. and Yap, R. H. C. 1995. Linear equation solving for constraint logic programming. In Proceedings of the 12th International Conference on Logic Programming. MIT, Tokyo, Japan, 33–47.Google Scholar
Cooper, M. C., Cohen, D. A. and Jeavons, P. G. 1994. Characterizing tractable constraints. Artificial Intelligence 65, 2, 347–361.CrossRefGoogle Scholar
David, P. 1995. Using pivot consistency to decompose and solve functional CSPs. Journal of Artificial Intelligence Research 2, 447–474.CrossRefGoogle Scholar
Dechter, R. 1999. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence 113, 1–2, 41–85.CrossRefGoogle Scholar
Escala-Imas, G. and Ghallab, M. 1988. A practically efficient and almost linear unification algorithm. Artificial Intelligence 36, 2, 249–263.CrossRefGoogle Scholar
Jaffar, J. and Maher, M. J. 1994. Constraint Logic Programming. Journal of Logic Programming 19/20, 503–581.CrossRefGoogle Scholar
Jaffar, J., Michaylov, S., Stuckey, P. J. and Yap, R. H. C. 1992. The CLP(ℛ) language and system. ACM Transactions on Programming Languages and Systems 14, 3, 339–395.CrossRefGoogle Scholar
Kirousis, L. M. 1993. Fast parallel constraint satisfaction. Artificial Intelligence 64, 1, 147–160.CrossRefGoogle Scholar
Liu, B. 1995. Increasing functional constraints need to be checked only once. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. IJCAI Inc., Montréal, Québec, Canada, 119–125.Google Scholar
Paterson, M. S. and Wegman, M. N. 1978. Linear unification. Journal of Computer and System Sciences 16, 2, 158–167.CrossRefGoogle Scholar
Schulte, C. and Tack, G. 2005. Views and iterators for generic constraint implementations. In Recent Advances in Constraints, Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming. Springer, Lausanne, Switzerland, 118–132.Google Scholar
Stallman, R. M. and Sussman, G. J. 1977. Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence 9, 2, 135–196.Google Scholar
Van Hentenryck, P., Deville, Y. and Teng, C. M. 1992. A generic arc-consistency algorithm and its specializations. Artificial Intelligence 57, 2–3, 291–321.CrossRefGoogle Scholar
Zhang, Y. and Yap, R. H. C. 2002. Incrementally solving functional constraints. In Proceedings of the Eighteenth National Conference on Artificial Intelligence. AAAI, Edmonton, Alberta, Canada, 973–974.Google Scholar
Zhang, Y., Yap, R. H. C. and Jaffar, J. 1999. Functional elimination and 0/1/all constraints. In Proceedings of the Sixteenth National Conference on Artificial Intelligence. AAAI, Orlando, Florida, 275–281.Google Scholar
Zhang, Y., Yap, R. H. C., Li, C. and Marisetti, S. 2008. Efficient algorithms for functional constraints. In Proceedings of the 24th International Conference on Logic Programming. Springer, Udine, Italy, 606–620.Google Scholar