Interval-valued soft constraint problems

Constraints and quantitative preferences, or costs, are very useful for modelling many real-life problems. However, in many settings, it is difficult to specify precise preference values, and it is much more reasonable to allow for preference intervals. We define several notions of optimal solutions for such problems, providing algorithms to find optimal solutions and also to test whether a solution is optimal. Most of the time these algorithms just require the solution of soft constraint problems, which suggests that it may be possible to handle this form of uncertainty in soft constraints without significantly increasing the computational effort needed to reason with such problems. This is supported also by experimental results. We also identify classes of problems where the same results hold if users are allowed to use multiple disjoint intervals rather than a single one.