Abstract
k-consistency operations in constraint satisfaction problems (CSPs) render constraints more explicit by solving size-k subproblems and projecting the information thus obtained down to low-order constraints. We generalise this notion of k-consistency to valued constraint satisfaction problems (VCSPs) and show that it can be established in polynomial time when penalties lie in a discrete valuation structure.
A generic definition of consistency is given which can be tailored to particular applications. As an example, a version of high-order consistency (face consistency) is presented which can be established in low-order polynomial time given certain restrictions on the valuation structure and the form of the constraint graph.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bertele, U., & Brioschi, F. (1972). Nonserial Dynamic Programming. Academic Press, New York, NY, USA.
Bistarelli, S., Fargier, H., Montanari, U., Rossi, F., Schiex, T., & Verfaillie, G. (1999). Semiring-based CSPs and valued CSPs: Frameworks, properties and comparison. Constraints 4: 199–240.
Cooper, M. C. (1990). An optimal k-consistency algorithm. Artif. Intell. 41: 89–95.
Cooper, M. C. (1993). Interpretation of line drawings of complex objects. Image Vis. Comput. 11(2): 82–90.
Cooper, M. C. (1999). Linear-time algorithms for testing the realisability of line drawings of curved objects. Artif. Intell. 108: 31–67.
Cooper, M. C. (2003). Reduction operations in fuzzy and valued constraint satisfaction. Fuzzy Sets Syst. 134: 311–342.
Cooper, M. C. (2004). Cyclic consistency: A local reduction operation for binary valued constraints. Artif. Intell. 155(1–2): 69–92.
Cooper M. C. (2005). High-Order Consistency in Valued Constraint Satisfaction. Internal Report, IRIT, Université Toulouse III.
Cooper, M. C., & Schiex, T. (2004). Arc consistency for soft constraints. Artif. Intell. 154(1–2): 199–227.
Dechter, R. (1997). Mini-buckets: A general scheme for generating approxiamtions in automated reasoning. In Proc. IJCAI-97, Nagoya, Japan, pages 1297–1303.
Dechter, R. (2003). Constraint Processing. San Mateo, CA: Morgan Kaukmann.
Dechter, R., & Pearl, J. (1988). Network-based heuristics for constraint satisfaction problems. Artif. Intell. 34: 1–38.
Fargier, H., & Lang, J. (1993). Uncertainty in constraint satisfaction problems: A probabilistic approach. In Proc. ECSQARU, Springer-Verlag, LNCS 747, pages 97–104.
Fargier, H., Lang, J., & Schiex, T. (1993). Selecting preferred solutions in Fuzzy Constraint Satisfaction Problems. In Proc. of the 1st European Congress on Fuzzy and Intelligent Technologies.
Larkin, D. (2003). Semi-Independent Partitioning: A method for bounding the solution to COP’s. In Proc. Principles and Practice of Constraint Propgramming—CP 2003, Springer-Verlag, LNCS 2833, pages 894–898.
Larrosa, J. (2002). On arc and node consistency in weighted CSP. In Proc. AAAI‘02.
Larrosa, J., & Schiex, T. (2003). In the Quest of the Best Form of Local Consistency for Weighted CSP. IJCAI.
Rosenfeld, A., Hummel, R., & Zucker, S. (1976). Scene labelling by relaxation operations. IEEE Trans. Syst. Man Cybern. 6(6): 173–184.
Schiex, T. (2000). Arc consistency for soft constraints. In Proc. CP’2000, LNCS 1894, pages 411–424.
Schiex, T., Fargier, H., & Verfaillie, G. (1995). Valued constraint satisfaction problems: hard and easy problems. In Proc. of the 14th IJCAI, Montreal, Canada, pages 631–637.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cooper, M.C. High-Order Consistency in Valued Constraint Satisfaction. Constraints 10, 283–305 (2005). https://doi.org/10.1007/s10601-005-2240-3
Issue Date:
DOI: https://doi.org/10.1007/s10601-005-2240-3