Abstract
In [8], Freuder defined interchangeability for classical Constraint Satisfaction Problems (CSPs). Recently [2], we extended the definition of interchangeability to Soft CSPs and we introduced two notions of relaxation based on degradation δ and on threshold α (δneighborhood interchangeability (δ NI)and α neighborhood interchangeability ( α NI)). In this paper we extend the study introduced in [11] and we analyze the presence of the relaxed version of interchangeability in random soft CSPs. We give a short description of the implementation we used to compute interchangeabilities and to make the tests. The experiments show that there is high occurrence of α NI and δ NI interchangeability around optimal solution in fuzzy CSPs and weighted CSPs. Thus, these algorithms can be used successfully in solution update applications. Moreover, it is also showed that NI interchangeability can well approximate full interchangeability (FI).
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
Benson, B.W., Freuder, E.: Interchangeability preprocessing can improve forward checking search. In: Proc. of the 10th ECAI (1992)
Bistarelli, S., Faltings, B., Neagu, N.: A definition of interchangeability for soft csps. In: Proc. ERCIM/CologNet Workshop on Constraint - Selected Papers. LNCS (LNAI), Springer, Heidelberg (2002) (to appear)
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Solving and Optimization. Journal of the ACM 44(2) (1997)
Bruchez, E., Torrens, M.: Java constraint library (1996), http://liawww.epfl.ch/torrens/Project/JCL/
Choueiry, B., Faltings, B., Weigel, R.: Abstraction by Interchangeability in Resource Allocation. In: Proc. of the 14th IJCAI 1995, Montreal, Canada, pp. 1694–1701 (1995)
Choueiry, B.Y.: Abstraction Methods for Resource Allocation. PhD thesis, EPFL PhD Thesis no 1292 (1994)
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 (1993)
Freuder, E.C.: Eliminating interchangeable values in constraint satisfaction problems. In: Proc. of AAAI 1991 (1991)
Freuder, E.C., Wallace, R.J.: Partial constraint satisfaction. Artificial Intelligence Journal 58 (1992)
Haselbock, A.: Exploiting interchangeabilities in constraint satisfaction problems. In: Proc. of the 13th IJCAI (1993)
Neagu, N., Bistarelli, S., Faltings, B.: On the computation of local interchangeability in soft constraint satisfaction problems. In: Proc. of the 16th International FLAIRS Conference - Special Track on Constraint Solving and Programming, St. Augustine, Florida, USA, AAAI Press, Menlo Park (2003)
Neagu, N., Faltings, B.: Constraint Satisfaction for Case Adaptation. In: Proc. of the workshop sesion, ICCBR 1999 (1999)
Ruttkay, Z.: Fuzzy constraint satisfaction. In: Proc. 3rd IEEE International Conference on Fuzzy Systems (1994)
Schiex, T., Fargier, H., Verfaille, G.: Valued Constraint Satisfaction Problems: Hard and Easy Problems. In: Proc. IJCAI 1995 (1995)
Weigel, R., Faltings, B.: Interchangeability for case adaptation in configuration problems. In: Proc. of the AAAI, Spring Symposium on Multimodal Reasoning, Stanford, CA (1998), TR SS-98-04
Weigel, R., Faltings, B.: Compiling constraint satisfaction problems. Artificial Intelligence 115 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Neagu, N., Bistarelli, S., Faltings, B. (2004). Experimental Evaluation of Interchangeability in Soft CSPs. In: Apt, K.R., Fages, F., Rossi, F., Szeredi, P., Váncza, J. (eds) Recent Advances in Constraints. CSCLP 2003. Lecture Notes in Computer Science(), vol 3010. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24662-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-24662-6_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21834-0
Online ISBN: 978-3-540-24662-6
eBook Packages: Springer Book Archive