Relaxations of semiring constraint satisfaction problems |
| |
Authors: | Louise Leenen Thomas Meyer |
| |
Affiliation: | a Decision Systems Laboratory, School of Computer Science and Software Engineering, University of Wollongong, Australia b Meraka Institute, CSIR, Pretoria, South Africa |
| |
Abstract: | The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201-236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects. |
| |
Keywords: | Semiring constraint satisfaction problems Over-constrained problems Preferences and soft constraints Combinatorial problems |
本文献已被 ScienceDirect 等数据库收录! |
|