Istituto di Informatica e Telematica     
Bistarelli S. On the Computation of Local Interchangeability in Soft Constraint Satisfaction Problems. In: 16th International FLAIRS Conference FLAIR03 (Saint Augustine, 2003). Proceedings, pp. 1 - 5. Springer, 2003.
Freuder in (1991) de£ned interchangeability for classical Constraint Satisfaction Problems (CSPs). Recently (2002), we extended the de£nition of interchangeability to Soft CSPs and we introduced two notions of relaxations based on degradation ± and on threshold ® (±neighborhood interchangeability (®NI )and ®neighborhood interchangeability ±NI ). In this paper we study the presence of these relaxed version of interchangeability in random soft CSPs. We give a 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 CSP and weighted CSPs. Thus, these algorithms can be used succesfully in solution update applications. Moreover, it is also showed that NI interchangeability can well approximate full interchangeability (FI ).
Subject interchangeability
Soft Constraint

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional