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 un-certainty and imprecision that is often found in real-life problems. We then define several notions of optimal so-lutions 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 uncer-tainty in soft constraints problems, it is important to no-tice 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 re-sults hold if users are allowed to use multiple disjoint intervals rather than a single one