Abstract
We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators. Adapting the generalized view of local consistency in semiring-based constraint satisfaction problems (SCSPs), we define constraint hierarchy k -consistency (CH-k-C) and give a CH-2-C enforcement algorithm. We demonstrate how the CH-2-C algorithm can be seamlessly integrated into the ordinary branch-and-bound algorithm to make it a finite domain CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other finite domain CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions.
We thank the anonymous referees for their constructive comments. The work described in this paper was substantially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region (Project no. CUHK4358/02E).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Badros, G.J., Borning, A., Stuckey, P.J.: The Cassowary linear arithmetic constraint solving algorithm. ACM Transactions on Computer-Human Interaction 8(4), 267–306 (2001)
Bessière, C., Freuder, E.C., Régin, J.C.: Using inference to reduce arc consistency computation. In: Proceedings of IJCAI 1995, pp. 592–598 (1995)
Bistarelli, S., Codognet, P., Hui, H.K.C., Lee, J.H.M.: Solving finite domain constraint hierarchies by local consistency and tree search. In: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (2 pages) (2003) (to appear)
Bistarelli, S., Georget, Y., Lee, J.H.M.: Capturing (fuzzy) constraint hierarchies in semiringbased constraint satisfaction (unpublished Manuscript) (1999), http://www.sci.unich.it/~bista/drafts/soft-fuzzyCH.pdf
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint solving and optimization. Journal of the ACM 44(2), 201–236 (1997)
Borning, A., Anderson, R., Freeman-Benson, B.: Indigo: A local propagation algorithm for inequality constraints. In: Proceedings of the 1996 ACM Symposium on User Interface Software and Technology, pp. 129–136 (1996)
Borning, A., Freeman-Benson, B.: Ultraviolet: A constraint satisfaction algorithm for interactive graphics. Constraints: An International Journal 3(1), 9–32 (1998)
Borning, A., Freeman-Benson, B., Wilson, M.: Constraint hierarchies. Lisp and Symbolic Computation 5(3), 223–270 (1992)
Borning, A., Marriott, K., Stuckey, P., Xiao, Y.: Solving linear arithmetic constraints for user interface applications. In: Proceedings of the ACM Symposium on User Interface Software and Technology, pp. 87–96 (1997)
Cooper, M.C.: Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and Systems 134(3), 311–342 (2003)
Freeman-Benson, B.: Efficiency of DeltaStar. Private Communication (April 2002)
Freeman-Benson, B., Maloney, J., Borning, A.: An incremental constraint solver. Communications of the ACM 33(1), 54–63 (1990)
Freeman-Benson, B., Wilson, M., Borning, A.: DeltaStar: A general algorithm for incremental satisfaction of constraint hierarchies. In: The 11th Annual IEEE Phoenix Conference on Computers and Communications, pp. 561–568 (1992)
Georget, Y., Codognet, P.: Compiling semiring-based constraints with clp(FD,S). In: Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (1998)
Grant, S.A., Smith, B.M.: The phase transition behavior of maintaining arc consistency. In: Proceedings of ECAI 1996, pp. 175–179 (1996)
Henz, M., Lim, Y.F., Lua, S.C., Shi, X.P., Walser, J.P., Yap, R.H.C.: Solving hierarchical constraints over finite domains. In: Sixth International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida (2000)
Hosobe, H., Matsuoka, S., Yonezawa, A.: Generalized local propagation: A framework for solving constraint hierarchies. In: Proceedings of the Second International Conference on Principles and Practice of Constraint Programming, pp. 237–251 (1996)
Hosobe, H., Miyashita, K., Takahashi, S., Matsuoka, S., Yonezawa, A.: Locally simultaneous constraint satisfaction. In: Borning, A. (ed.) PPCP 1994. LNCS, vol. 874, pp. 51–62. Springer, Heidelberg (1994)
Mackworth, A.K.: Consistency in networks of relations. AI Journal 8(1), 99–118 (1977)
Menezes, F., Barahona, P., Codognet, P.: An incremental hierarchical constraint solver. In: First Workshop on Principle and Practice of Constraint Processing (1993)
Nelder, J.A., Mead, R.: A simplex method for function minimization. The Computer Journal 7, 308–313 (1965)
Sannella, M.: The SkyBlue constraint solver and its applications. In: Saraswat, V.A., Hentenryck, P.V. (eds.) Proceedings of the First Workshop on Principles and Practice of Constraint Programming. MIT Press, Cambridge (1994)
Schiex, T.: Arc consistency for soft constraints. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 411–424. Springer, Heidelberg (2000)
Steele, G.L., Sussman, G.J.: Constraints. In: APL conference proceedings part 1, pp. 208–225 (1979)
Wallace, R.J.: Directed arc consistency preprocessing. In: Meyer, M. (ed.) Constraint Processing. LNCS, vol. 923, pp. 121–137. Springer, Heidelberg (1995)
Wilson, M., Borning, A.: Hierarchical constraint logic programming. Journal of Logic Programming 16, 277–318 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bistarelli, S., Codognet, P., Hui, KC., Lee, J.H.M. (2003). Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive