An overview of valued CSP and related results
Résumé
The Constraint Satisfaction Problem (CSP) framework is getting more and more widely used to represent and solve constraint-based problems in several areas: automatic or aided decision, scheduling, diagnosis, constraint programming... This wide range of applications has brought to light some weaknesses of the intial framework. Among these, one of the most important one is the problem of "facing inconsistency" i.e..the fact that the translation of a real problem for which a solution is sought yields a CSP with no solution. Several different but closely related answers, relying on the idea of "soft constraints", have been considered recently. To better identify what distinguishes and relates all these approaches, two general algebraic generalizations have been defined. This paper presents the so-called valued CSP generalization.