Interval-valued soft constraint problems
Pini, Maria Silvia
Venable, Kristin Brent
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.
Soft constraints , Preferences , Interval reasoning , Uncertainty
Gelain, M; Pini, MS; Rossi, F; Venable, KB; Wilson, N; (2010) 'Interval-valued Soft Constraint Problems'. Annals of Mathematics and Artificial Intelligence, 58 (3/4): 261–298. doi: 10.1007/s10472-010-9203-0
© Springer Science+Business Media B.V. 2010. The final publication is available at http://link.springer.com/article/10.1007%2Fs10472-010-9203-0