Imprecise soft constraint problems

We define interval-valued soft constraints, where users can associate an interval of preference values, rather than a single value, to each instantiation of the variables of the constraints. This allows us to model a form of uncertainty and imprecision that is often found in real-life problems. We then define several notions of optimal solutions for such problems, providing algorithms to find optimals and also to test whether a solution is optimal. Besides the usefulness of the algorithms, that can be the base for an environment where to reason with uncertainty in soft constraints problems, it is important to notice that most of the times these algorithms require the solution of a soft constraint problem. This means that it is possible to handle uncertainty in soft constraints without increasing the computational effort to reason with such problems. We also show that the same results hold if users are allowed to use multiple disjoint intervals rather than a single one.