Skip to main content
Log in

Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

In this paper we describe and compare two frameworks for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. One is based on a semiring, and the other one on a totally ordered commutative monoid. While comparing the two approaches, we show how to pass from one to the other one, and we discuss when this is possible. The two frameworks have been independently introduced in ijcai95,jacm and schiex-ijcai95.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Bistarelli (1994). Programmazione con vincoli pesati e ottimizzazione (in italian). Dipartimento di Informatica, Universit`a di Pisa, Italy.

    Google Scholar 

  2. S. Bistarelli, U. Montanari, and F. Rossi (1995). Constraint solving over semirings. In Proc. IJCAI95. Morgan Kaufman.

  3. S. Bistarelli, U. Montanari and F. Rossi (1997). Semiring-based constraint solving and optimization. Journal of the ACM 44(2): 201–236.

    Google Scholar 

  4. S. Bistarelli, U. Montanari, and F. Rossi (1997). Semiring-based constraint logic programming. In Proc. IJCAI97. Morgan Kaufman.

  5. A. Borning, M. Maher, A. Martindale, and M. Wilson (1989). Constraint hierarchies and logic programming. In M. Martell, Levi G., editors, Proc. 6th ICLP. MIT Press.

  6. R. Dechter, A. Dechter, and J. Pearl (1990). Optimization in constraint networks. In R. M. Oliver and J. Q. Smith, editors, Influence Diagrams, Belief Nets and Decision Analysis, chapter 18, pages 411–425. John Wiley & Sons Ltd.

  7. D. Dubois and H. Prade (1982). A class of fuzzy measures based on triangular norms. a general framework for the combination of uncertain information. Int. Journal of Intelligent Systems 8(1): 43–61.

    Google Scholar 

  8. D. Dubois, H. Fargier, and H. Prade (1993). The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In Proc. IEEE Int. Conf. on Fuzzy Systems. IEEE.

  9. H. Fargier and J. Lang (1993). Uncertainty in constraint satisfaction problems: a probabilistic approach. Proc. ECSQARU. Springer-Verlag, LNCS 747.

    Google Scholar 

  10. H. Fargier and J. Lang and T. Schiex (1993). Selecting preferred solutions in fuzzy constraint satisfaction problems. Proc. 1st European Congress on Fuzzy and Intelligent Technologies (EUFIT).

  11. E. Freuder (1978). Synthesizing constraint expressions. CACM 21(11).

  12. E. Freuder (1988). Backtrack-free and backtrack-bounded search. In Kanal and Kumar, editors, Search in Artificial Intelligence, Springer-Verlag.

  13. E. Freuder and R. Wallace (1992). Partial constraint satisfaction. Artificial Intelligence Journal 58.

  14. M. Garey, D. Johnson, and L. Stockmeyer (1976). Some simplified NP-complete graph problems. Theoretical Computer Science 1: 237–267.

    Google Scholar 

  15. Y. Georget, and P. Codognet (1998). Compiling semiring-based constraints with clp(FD,S). Proc. CP98, Springer Verlag, LNCS 1520.

    Google Scholar 

  16. S. de Givry, G. Verfaillie and T. Schiex (1997). Bounding the optimum of constraint optimization problems. Proc. of the Third International Conference on Principles and Practice of Constraint Programming, pages 405–419, Schloss Hagenberg, Austria.

  17. P. Hubbe and E. Freuder (1992). An efficient cross-product representation of the constraint satisfaction problem search space. In Proc. of AAAI-92, pages 421–427, San Jose, CA.

  18. V. Kumar (1992). Algorithms for constraint satisfaction problems: a survey. AI Magazine 13(1).

  19. J. Jaffar and J.L. Lassez (1987). Constraint logic programming. Proc. POPL, ACM.

  20. M. Krentel (1988). The complexity of optimization problems. Journal of Computer and System Sciences 36: 490–509.

    Google Scholar 

  21. J. Larrosa and P. Meseguer (1996). Exploiting the use ofDACinMAX-CSP. Proc. of the Second International Conference on Principles and Practice of Constraint Programming, pages 308–322, Cambridge (MA).

  22. J. Larrosa, P. Meseguer, T. Schiex, and G. Verfaillie (1998). Reversible DAC and other improvements for solving Max-CSP. Proc. of the National Conf. on Artificial Intelligence (AAAI'98), pages 347–352, Madison (WI).

  23. J. Larrosa, P. Meseguer, and T. Schiex (1999). Maintaining reversible DAC for Max-CSP. Artificial Intelligence Journal, 107(1).

  24. A. Mackworth (1977). Consistency in networks of relations. Artificial Intelligence Journal, 8(1).

  25. A. Mackworth (1988). Encyclopedia of AI, chapter Constraint Satisfaction, pages 205–211. Springer Verlag.

  26. A. Mackworth and E. Freuder (1985). The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence Journal 25.

  27. U. Montanari (1974). Networks of constraints: Fundamental properties and application to picture processing. Information Science 7.

  28. U. Montanari and F. Rossi (1991). Constraint relaxation may be perfect. Artificial Intelligence Journal 48:143–170.

    Google Scholar 

  29. H. Moulin (1988). Axioms for Cooperative Decision Making. Cambridge University Press.

  30. B. A. Nadel (1989). Constraint satisfaction algorithms. Comput. Intell. 5(4): 188–224.

    Google Scholar 

  31. C. M. Papadimitriou (1994). Computational Complexity. Addison Wesley Publishing Company.

  32. A. Rosenfeld, R. Hummel, and S. Zucker (1976). Scene labelling by relaxation operations. IEEE Trans. on Sys., Man, and Cyb. 6(6).

  33. Z. Ruttkay (1994). Fuzzy constraint satisfaction. Proc. 3rd Int. Conf. on Fuzzy Systems.

  34. T. Schiex (1992). Possibilistic constraint satisfaction problems, or “How to handle soft constraints?”. Proc. 8th Conf. of Uncertainty in AI.

  35. T. Schiex, H. Fargier, and G. Verfaillie (1995). Valued constraint satisfaction problems: Hard and easy problems. In Proc. IJCAI95. Morgan Kaufmann.

  36. G. Shafer (1991). An axiomatic study of computation in hypertrees. Working paper 232, University of Kansas, School of Business, Lawrence.

    Google Scholar 

  37. P. Shenoy (1991). Valuation-based systems for discrete optimization. In Bonissone, Henrion, Kanal and Lemmer, editors, Uncertainty in AI. North-Holland Publishers.

  38. P. Shenoy (1994). Valuation-based systems: A framework for managing uncertainty in expert systems. In L. Zadeh and J. Kacprzyk, editors, Fuzzy Logic for the Management of Uncertainty. Wiley.

  39. L. Shapiro and R. Haralick (1981). Structural descriptions and inexact matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 3: 504–519.

    Google Scholar 

  40. P. Snow and E. Freuder (1990). Improved relaxation and search methods for approximate constraint satisfaction with a maximin criterion. In Proc. of the 8th Biennal Conf. of the Canadian Society for Comput. Studies of Intelligence, pages 227–230.

  41. G. Verfaillie, M. Lematre, and T. Schiex (1996). Russian doll search. In Proc. of AAAI-96, pages 181–187, Portland (OR).

  42. R. J. Wallace (1994). Directed arc consistency preprocessing as a strategy for maximal constraint satisfaction. In the Proc. of ECAI'94 Workshop on Constraint Processing. pages 69–77. Also available in LNCS 923, pp. 121–138 (1995).

  43. L. Zadeh (1975). Calculus of fuzzy restrictions. In K. Tanaka, L.A. Zadeh, K.S. Fu and M. Shimura, editors, Fuzzy sets and their applications to cognitive and decision processes. Academic Press.

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bistarelli, S., Montanari, U., Rossi, F. et al. Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison. Constraints 4, 199–240 (1999). https://doi.org/10.1023/A:1026441215081

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1026441215081

Navigation