Semiring-based constraint satisfaction and optimization. Bistarelli, S., Ugo, M., & Francesca, R. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 44:201–236, 1997. doi abstract bibtex We introduce a general framework for constraint satisfaction and optimization where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where the set of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations (+ and X) model constraint projection and combination respectively. Local consistency algorithms, as usually used for classical CSPs, can be exploited in this general framework as well, provided that certain conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving and optimization. schemes, thus allowing one to both formally justify many informally taken choices in existing schemes, and to prove that local consistency techniques can be used also in newly defined schemes.
@article{
11391_120843,
author = {Bistarelli, Stefano and Ugo, Montanari and Francesca, Rossi},
title = {Semiring-based constraint satisfaction and optimization},
year = {1997},
journal = {JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY},
volume = {44},
abstract = {We introduce a general framework for constraint satisfaction and optimization where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where the set of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations (+ and X) model constraint projection and combination respectively. Local consistency algorithms, as usually used for classical CSPs, can be exploited in this general framework as well, provided that certain conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving and optimization. schemes, thus allowing one to both formally justify many informally taken choices in existing schemes, and to prove that local consistency techniques can be used also in newly defined schemes.},
keywords = {constraint solving, dynamic programming, local consistency, non-crisp constraint reasoning},
doi = {10.1145/256303.256306},
pages = {201--236}
}
Downloads: 0
{"_id":"EaefkDYc9GkQvz8Xc","bibbaseid":"bistarelli-ugo-francesca-semiringbasedconstraintsatisfactionandoptimization-1997","author_short":["Bistarelli, S.","Ugo, M.","Francesca, R."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Bistarelli"],"firstnames":["Stefano"],"suffixes":[]},{"propositions":[],"lastnames":["Ugo"],"firstnames":["Montanari"],"suffixes":[]},{"propositions":[],"lastnames":["Francesca"],"firstnames":["Rossi"],"suffixes":[]}],"title":"Semiring-based constraint satisfaction and optimization","year":"1997","journal":"JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY","volume":"44","abstract":"We introduce a general framework for constraint satisfaction and optimization where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where the set of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations (+ and X) model constraint projection and combination respectively. Local consistency algorithms, as usually used for classical CSPs, can be exploited in this general framework as well, provided that certain conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving and optimization. schemes, thus allowing one to both formally justify many informally taken choices in existing schemes, and to prove that local consistency techniques can be used also in newly defined schemes.","keywords":"constraint solving, dynamic programming, local consistency, non-crisp constraint reasoning","doi":"10.1145/256303.256306","pages":"201–236","bibtex":"@article{\n\t11391_120843,\n\tauthor = {Bistarelli, Stefano and Ugo, Montanari and Francesca, Rossi},\n\ttitle = {Semiring-based constraint satisfaction and optimization},\n\tyear = {1997},\n\tjournal = {JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY},\n\tvolume = {44},\n\tabstract = {We introduce a general framework for constraint satisfaction and optimization where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where the set of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations (+ and X) model constraint projection and combination respectively. Local consistency algorithms, as usually used for classical CSPs, can be exploited in this general framework as well, provided that certain conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving and optimization. schemes, thus allowing one to both formally justify many informally taken choices in existing schemes, and to prove that local consistency techniques can be used also in newly defined schemes.},\n\tkeywords = {constraint solving, dynamic programming, local consistency, non-crisp constraint reasoning},\n\tdoi = {10.1145/256303.256306},\t\n\tpages = {201--236}\n}\n","author_short":["Bistarelli, S.","Ugo, M.","Francesca, R."],"key":"11391_120843","id":"11391_120843","bibbaseid":"bistarelli-ugo-francesca-semiringbasedconstraintsatisfactionandoptimization-1997","role":"author","urls":{},"keyword":["constraint solving","dynamic programming","local consistency","non-crisp constraint reasoning"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"article","biburl":"http://www.dmi.unipg.it/~bista/papers/pubblicazioni.bib","dataSources":["GhB5rb8JzW6az3exo"],"keywords":["constraint solving","dynamic programming","local consistency","non-crisp constraint reasoning"],"search_terms":["semiring","based","constraint","satisfaction","optimization","bistarelli","ugo","francesca"],"title":"Semiring-based constraint satisfaction and optimization","year":1997}