Abstract:
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 prob-
lems, 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.
