associated to a range of possible values, that may be smaller than the whole range of preference values. For such problems, we intend to define several notions of optimality, among which necessarily and possibly optimal solutions are just two examples, and to develop specific elicitation strategies for each of them. We are also studying soft constraint problems when no preference is missing, but some of them are unstable, and have associated a range of possible alternative values.

To model fuzzy CSPs, we have not used traditional fuzzy set theory [3], but soft CSPs [1], since we intend to apply our work also to non-fuzzy CSPs. In fact, we plan to consider incomplete weighted constraint problems as well as different heuristics for choosing the next variable during the search. All algorithms with What=all are not tied to fuzzy CSPs and are reasonably efficient. Moreover, we intend to build solvers based on local search and variable elimination methods. Finally, we want to add elicitation costs and to use them also to guide the search, as done in [10] for hard CSPs.

## Acknowledgements

This work has been partially supported by Italian MIUR PRIN project "Constraints and Preferences" (n. 2005015491). The last author is funded by the Department of Broadband, Communications and the Digital Economy, and the Australian Research Council.

## References

1. S. Bistarelli, U. Montanari, and F. Rossi. Semiring-based constraint solving and optimization. *JACM*, 44(2):201–236, mar 1997.

2. R. Dechter and A. Dechter. Belief maintenance in dynamic constraint networks. In *AAAI*,
pages 37–42, 1988.

3. D. Dubois and H. Prade. *Fuzzy sets and Systems - Theory and Applications*. Academic Press, 1980.

4. B. Faltings and S. Macho-Gonzalez. Open constraint satisfaction. In CP, volume 2470 of LNCS, pages 356–370. Springer, 2002.

5. B. Faltings and S. Macho-Gonzalez. Open constraint optimization. In CP, volume 2833 of LNCS, pages 303–317. Springer, 2003.

6. B. Faltings and S. Macho-Gonzalez. Open constraint programming. *AI Journal*, 161(12):181–208, 2005.

7. M. Gelain, M. S. Pini, F. Rossi, and K. B. Venable. Dealing with incomplete preferences in soft constraint problems. In *Proc. CP'07*, volume 4741 of *LNCS*, pages 286–300. Springer, 2007.

8. L. Khatib, P. Morris, R. Morris, F. Rossi, A. Sperduti, and K. Brent Venable. Solving and learning a tractable class of soft temporal problems: theoretical and experimental results. AI
Communications, 20(3), 2007.

9. E. Lamma, P. Mello, M. Milano, R. Cucchiara, M. Gavanelli, and M. Piccardi. Constraint propagation and value acquisition: Why we should do it interactively. In *IJCAI*, pages 468– 477, 1999.

10. N. Wilson, D. Grimes, and E. C. Freuder. A cost-based model and algorithms for interleaving solving and elicitation of csps. In *Proc. CP'07*, volume 4741 of *LNCS*, pages 666–680.

Springer, 2007.