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 the notions of threshold α and degradation δ for substitutability and interchangeability. 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 δ.
Theorems, algorithms to compute (δ/α)interchangeable sets of values, and a more general treatment of all the ideas presented in this paper can be found in [2].
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Bistarelli, S.: Soft Constraint Solving and programming: a general framework. PhD thesis, Dipartimento di Informatica, Università di Pisa, Italy (2001) TD-2/01
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. (2002) Selected papers will be published in LNCS series
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Solving and Optimization. J. ACM 44 (1997)
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Logic Programming: Syntax and Semantics. TOPLAS ACM 23 (2001)
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)
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). Volume 747 of LNCS. (1993)
Freuder, E. C.: Eliminating interchangeable values in constraint satisfaction problems. In: Proc. of AAAI-91. (1991)
Freuder, E., Wallace, R.: Partial constraint satisfaction. AI Journal 58 (1992)
Haselbock, A.: Exploiting interchangeabilities in constraint satisfaction problems. In: Proc. of the 13th IJCAI. (1993)
Neagu, N., Faltings, B.: Exploiting interchangeabilities for case adaptation. In: In Proc. of the 4th ICCBR01. (2001)
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. IJCAI95. (1995)
Weigel, R., Faltings, B.: Interchangeability for case adaptation in configuration problems. In: Proc. of the AAAI98 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
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bistarelli, S., Faltings, B., Neagu, N. (2002). Interchangeability in Soft CSPs. In: Van Hentenryck, P. (eds) Principles and Practice of Constraint Programming - CP 2002. CP 2002. Lecture Notes in Computer Science, vol 2470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46135-3_53
Download citation
DOI: https://doi.org/10.1007/3-540-46135-3_53
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44120-5
Online ISBN: 978-3-540-46135-7
eBook Packages: Springer Book Archive