1997/03/01 by Stefano Bistarelli, Ugo Montanari, Francesca Rossi · 3 citations
Computer Science · Mathematics · #Constraint Satisfaction and Optimization #Data Management and Algorithms #Rough Sets and Fuzzy Logic #Semiring #Constraint satisfaction problem #Local consistency #Constraint satisfaction #Mathematics #Constraint satisfaction dual problem #Mathematical optimization #Constraint logic programming #Constraint (computer-aided design) #Constraint programming #Tuple #Consistency (knowledge bases) #Set (abstract data type) #Domain (mathematical analysis) #Computer science #Discrete mathematics
paper · pdf · doi:10.1145/256303.256306
openalex publication_date 1997/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/04
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.