Skip to main content
SpringerLink
Log in

Interchangeability with thresholds and degradation factors for Soft CSPs

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs). We introduce two notions: threshold α and degradation factor δ for substitutability and interchangeability, ( α substitutability/interchangeability and δsubstitutability/interchangeabi-lity respectively). We show that they satisfy analogous theorems to the ones already known for hard constraints. In α interchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ. We give efficient algorithms to compute (δ/ α )interchangeable sets of values for a large class of SCSPs, and show an example of their application. Through experimental evaluation based on random generated problem we measure first, how often neighborhood interchangeable values are occurring, second, how well they can approximate fully interchangeable ones, and third, how efficient they are when used as preprocessing techniques for branch and bound search.

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

Access this article

Log in via an institution

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. Benson, B.W., Freuder, E.: Interchangeability preprocessing can improve forward checking search. In: Proc. of the 10th ECAI, pp. 28–30. Vienna, Austria (1992)

  2. Bistarelli, S., Fargier, H., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G.: Semiring-based CSPs and valued CSPs: basic properties and comparison. In: Over-Constrained Systems, number 1106 in LNCS. Springer-Verlag (1996)

  3. Bistarelli, S., Fargier, H., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G.: Semiring-based CSPs and Valued CSPs: frameworks, properties, and comparison. CONSTRAINTS: an international journal. Kluwer 4(3), 199–240 (1999)

    MathSciNet  MATH  Google Scholar 

  4. Bistarelli, S., Faltings, B., Neagu, N.: A definition of interchangeability for soft csps. In: Proc. of the Joint Workshop of the ERCIM Working Group on Constraints and the CologNet area on Constraint and Logic Programming on Constraint Solving and Constraint Logic Programming—Selected Papers, LNAI. Springer-Verlag (2002)

  5. Bistarelli, S., Faltings, B., Neagu, N.: Interchangeability in soft csps. In: Proc. of the 8th CP-2002, LNCS. Springer-Verlag (2002)

  6. Bistarelli, S.: Soft Constraint Solving and programming: a general framework. PhD thesis, Dipartimento di Informatica, Università di Pisa, Italy. TD-2/01 (2001)

  7. Bistarelli, S., Montanari, U., Rossi, F.: Constraint solving over semirings. In: Proc. IJCAI95. Morgan Kaufman, San Francisco, CA, USA (1995)

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint logic programming: syntax and semantics. ACM Trans. Program. Lang. Syst. 23, 1–29 (2001)

    Article  Google Scholar 

  10. Bistarelli, S., Montanari, U., Rossi, F.: Soft concurrent constraint programming. In: Proc. ESOP, April 6–14, 2002, LNCS. Springer-Verlag, Grenoble, France (2002)

  11. Choueiry, B., Faltings, B., Weigel, R.: Abstraction by Interchangeability in Resource Allocation. In: Proc. of the 14 th IJCAI-95, pp. 1694–1701. Montreal, Canada (1995)

  12. Choueiry, B.Y.: Abstraction methods for resource allocation. PhD thesis, EPFL PhD Thesis no. 1292 (1994)

  13. Choueiry, B.Y., Noubir, G.: On the computation of local interchangeability in discrete constraint satisfaction problems. In: AAAI/IAAI, pp. 326–333 (1998)

  14. Choueiry, B.Y., Noubir, G.: On the computation of local interchangeability in discrete constraint satisfaction problems. In: Proc. of AAAI-98, pp. 326–333. Madison, Wiscowsin (1998)

  15. Cooper, M.: Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets Syst. 134, 311–342 (2003)

    Article  MATH  Google Scholar 

  16. Dubois, D., Fargier, H., Prade, H.: The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In: Proc. IEEE International Conference on Fuzzy Systems, pp. 1131–1136. IEEE (1993)

  17. Fargier, H., Lang, J.: Uncertainty in constraint satisfaction problems: a probabilistic approach. In: Proc. European Conference on Symbolic and Qualitative Approaches to Reasoning and Uncertainty (ECSQARU), LNCS, vol. 747, pp. 97–104. Springer-Verlag (1993)

  18. Freuder, E.C.: Eliminating interchangeable values in constraint satisfaction problems. In: Proc. of AAAI-91, pp. 227–233. Anaheim, CA (1991)

  19. Freuder, E.C., Wallace, R.J.: Partial constraint satisfaction. Art. Intelligence 58, 21–70 (1992)

    Article  MathSciNet  Google Scholar 

  20. Haselbock, A.: Exploiting interchangeabilities in constraint satisfaction problems. In: Proc. of the 13th IJCAI, pp. 282–287 (1993)

  21. Neagu, N.: Studying interchangeability in constraint satisfaction problems. In: Van Hentenryck, P. (ed.) CP, Lecture Notes in Computer Science, vol. 2470, pp. 787–788. Springer (2002)

  22. Neagu, N.: Interchangeability in constraint satisfaction problems. PhD thesis, Ecole polytechnique fédérale de Lausanne EPFL, Lausanne (2003)

  23. Neagu, N., Faltings, B.: Constraint Satisfaction for Case Adaptation. In: Proc. of the Workshop on Case Adaptation in ICCBR-99. Munich (1999)

  24. Neagu, N., Faltings, B.: Exploiting interchangeabilities for case adaptation. In: Proc. of the 4th ICCBR01 (2001)

  25. Rossi, F., Pilar, I.: Abstracting Soft Constraints: Some Experimental Results. In: Joint Annual ERCIM/CoLogNet Workshop on Constraint and Logic Programming. Budapest, Hungary (2003)

  26. Ruttkay, Z.: Fuzzy constraint satisfaction. In: Proc. 3rd IEEE International Conference on Fuzzy Systems, pp. 1263–1268 (1994)

  27. Schiex, T.: Possibilistic constraint satisfaction problems, or “how to handle soft constraints?”. In: Proc. 8th Conf. of Uncertainty in AI, pp. 269–275 (1992)

  28. Schiex, T., Fargier, H., Verfaille, G.: Valued constraint satisfaction problems: hard and easy problems. In: Proc. IJCAI95, pp. 631–637. Morgan Kaufmann, San Francisco, CA, USA (1995)

  29. Weigel, R., Faltings, B.: Interchangeability for case adaptation in configuration problems. In: Proc. of the AAAI98 Spring Symposium on Multimodal Reasoning, TR SS-98-04. Stanford, CA (1998)

  30. Weigel, R., Faltings, B.: Compiling constraint satisfaction problems. Artif. Intell. 115, 257–289 (1999)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Istituto di Informatica e Telematica, CNR, Pisa, Italy

    S. Bistarelli

  2. Dipartimento di Matematica e Informatica, Università di Perugia, Perugia, Italy

    S. Bistarelli

  3. Ecole Polytechnique Fédérale de Lausanne (EPFL), School of Computer and Communication Sciences, Lausanne, Switzerland

    B. Faltings

  4. Claude Delorme Research Center, Air Liquide, JOUY en JOSAS, France

    N. Neagu

Authors
  1. S. Bistarelli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Faltings
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. N. Neagu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Bistarelli.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bistarelli, S., Faltings, B. & Neagu, N. Interchangeability with thresholds and degradation factors for Soft CSPs. Ann Math Artif Intell 67, 123–163 (2013). https://doi.org/10.1007/s10472-013-9348-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10472-013-9348-8

Keywords

Mathematics Subject Classification (2010)

Search

Navigation