Experimental Evaluation of Interchangeability in Soft CSPs. Bistarelli, S., Neagu, N., & Faltings, B. 2004. doi abstract bibtex 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 delta and on threshold alpha ((delta)neighborhood interchangeability ((NI)-N-delta)and (alpha)neighborhood interchangeability (alphaNI)). 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 alphaNI and (NI)-N-delta 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).
@conference{
11391_143137,
author = {Bistarelli, Stefano and Neagu, Nicoleta and Faltings, Boi},
title = {Experimental Evaluation of Interchangeability in Soft CSPs},
year = {2004},
publisher = {Springer},
journal = {LECTURE NOTES IN COMPUTER SCIENCE},
volume = {3010},
booktitle = {Recent Advances in Constraints, Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2003},
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 delta and on threshold alpha ((delta)neighborhood interchangeability ((NI)-N-delta)and (alpha)neighborhood interchangeability (alphaNI)). 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 alphaNI and (NI)-N-delta 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).},
doi = {10.1007/978-3-540-24662-6_8},
pages = {140--153}
}
Downloads: 0
{"_id":"4Epfxhy3DpbhdKDpw","bibbaseid":"bistarelli-neagu-faltings-experimentalevaluationofinterchangeabilityinsoftcsps-2004","author_short":["Bistarelli, S.","Neagu, N.","Faltings, B."],"bibdata":{"bibtype":"conference","type":"conference","author":[{"propositions":[],"lastnames":["Bistarelli"],"firstnames":["Stefano"],"suffixes":[]},{"propositions":[],"lastnames":["Neagu"],"firstnames":["Nicoleta"],"suffixes":[]},{"propositions":[],"lastnames":["Faltings"],"firstnames":["Boi"],"suffixes":[]}],"title":"Experimental Evaluation of Interchangeability in Soft CSPs","year":"2004","publisher":"Springer","journal":"LECTURE NOTES IN COMPUTER SCIENCE","volume":"3010","booktitle":"Recent Advances in Constraints, Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2003","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 delta and on threshold alpha ((delta)neighborhood interchangeability ((NI)-N-delta)and (alpha)neighborhood interchangeability (alphaNI)). 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 alphaNI and (NI)-N-delta 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).","doi":"10.1007/978-3-540-24662-6_8","pages":"140–153","bibtex":"@conference{\n\t11391_143137,\n\tauthor = {Bistarelli, Stefano and Neagu, Nicoleta and Faltings, Boi},\n\ttitle = {Experimental Evaluation of Interchangeability in Soft CSPs},\n\tyear = {2004},\n\tpublisher = {Springer},\n\tjournal = {LECTURE NOTES IN COMPUTER SCIENCE},\n\tvolume = {3010},\n\tbooktitle = {Recent Advances in Constraints, Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2003},\n\tabstract = {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 delta and on threshold alpha ((delta)neighborhood interchangeability ((NI)-N-delta)and (alpha)neighborhood interchangeability (alphaNI)). 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 alphaNI and (NI)-N-delta 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).},\n\tdoi = {10.1007/978-3-540-24662-6_8},\t\n\tpages = {140--153}\n}\n","author_short":["Bistarelli, S.","Neagu, N.","Faltings, B."],"key":"11391_143137","id":"11391_143137","bibbaseid":"bistarelli-neagu-faltings-experimentalevaluationofinterchangeabilityinsoftcsps-2004","role":"author","urls":{},"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"conference","biburl":"http://www.dmi.unipg.it/~bista/papers/pubblicazioni.bib","dataSources":["GhB5rb8JzW6az3exo"],"keywords":[],"search_terms":["experimental","evaluation","interchangeability","soft","csps","bistarelli","neagu","faltings"],"title":"Experimental Evaluation of Interchangeability in Soft CSPs","year":2004}