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 δ for substitutability and interchangeability, (αsubstituability/interchangeability4substituability/interchangeability 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 4interchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ.
We give efficient algorithms to compute (4/α) sets of values for a large class of SCSPs.
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
Benson, B., Freuder, E.: Interchangeability preprocessing can improve forward checking search. In: Proc. of the 10th ECAI, Vienna, Austria. (1992) 28–30
Bistarelli, S.: Soft Constraint Solving and programming: a general framework. PhD thesis, Dipartimento di Informatica, Università di Pisa, Italy (2001)
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 (1999)
Bistarelli, S., Montanari, U., Rossi, F.: Constraint Solving over Semirings. In: Proc. IJCAI95, San Francisco, CA, USA, Morgan Kaufman (1995)
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Solving and Optimization. Journal of the ACM 44 (1997) 201–236
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Logic Programming: Syntax and Semantics. ACM Transactions on Programming Languages and System (TOPLAS) 23 (2001) 1–29
Bistarelli, S., Montanari, U., Rossi, F.: Soft concurrent constraint programming. In: Proc. ESOP, 2002, Grenoble, France. LNCS, Springer-Verlag (2002)
Choueiry, B.Y.: Abstraction Methods for Resource Allocation. PhD thesis, EPFL PhD Thesis no 1292 (1994)
Choueiry, B.Y., Noubir, G.: On the computation of local interchangeability in discrete constraint satisfaction problems. In: Proc. of AAAI-98. (1998) 326–333
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, IEEE (1993) 1131–1136
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., Springer-Verlag (1993) 97–104
Freuder, E.C.: Eliminating interchangeable values in constraint satisfaction problems. In: Proc. of AAAI-91, Anaheim, CA (1991) 227–233
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) 282–287
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) 1263–1268
Schiex, T.: Possibilistic constraint satisfaction problems, or “how to handle soft constraints?”. In: Proc. 8th Conf. of Uncertainty in AI. (1992) 269–275
Schiex, T., Fargier, H., Verfaille, G.: Valued Constraint Satisfaction Problems: Hard and Easy Problems. In: Proc. IJCAI95, San Francisco, CA, USA, Morgan Kaufmann (1995) 631–637
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) 257–289
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bistarelli, S., Faltings, B., Neagu, N. (2003). Interchangeability in Soft CSPs. In: O’Sullivan, B. (eds) Recent Advances in Constraints. CologNet 2002. Lecture Notes in Computer Science, vol 2627. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36607-5_3
Download citation
DOI: https://doi.org/10.1007/3-540-36607-5_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00986-3
Online ISBN: 978-3-540-36607-2
eBook Packages: Springer Book Archive