On the Computation of Local Interchangeability in Soft Constraint Satisfaction Problems
Nicoleta Neagu, Stefano Bistarelli, Boi V. Faltings · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2003
Freuder in (1991) defined interchangeability for clas-sical Constraint Satisfaction Problems (CSPs). Re-cently (2002), we extended the definition of inter-changeability to Soft CSPs and we introduced two no-tions 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 descrip-tion of the implementation we used to compute interchange-abilities 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 in-terchangeability can well approximate full interchangeability (FI).