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 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint solving and optimization. JACM 44(2):201–236 (1997)
Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., Fargier, H.: Semiring-based CSPs and valued CSPs: frameworks, properties, and comparison. Constraints 4(3), 199–240 (1999)
Ceberio, M., Modave, F.: An interval-valued, 2-additive Choquet integral for multi-criteria decision making. In: IPMU’04 (2004)
Faltings, B., Macho-Gonzalez, S.: Open constraint programming. AI J. 161(1–2):181–208 (2005)
Fargier, H., Schiex, T., Verfaille, G.: Valued constraint satisfaction problems: hard and easy problems. In: IJCAI-95, pp. 631–637. Morgan Kaufmann, San Mateo (1995)
Gelain, M., Pini, M.S., Rossi, F., Venable, K.B.: Dealing with incomplete preferences in soft constraint problems. In: Proc. CP’07, volume 4741 of LNCS, pp. 286–300. Springer, New York (2007)
Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., Walsh, T.: Dealing with incomplete preferences in soft constraint problems. In: Proc. CP’08, volume 5202 of LNCS, pp. 402–417. Springer, New York (2008)
Macho González, S., Ansótegui, C., Meseguer, P.: On the relation among open, interactive and dynamic CSP. In: The Fifth Workshop on Modelling and Solving Problems with Constraints (IJCAI’05) (2005)
Meseguer, P., Rossi, F., Schiex, T.: Soft constraints. In: Rossi F., Van Beek P, Walsh T. (eds.) Handbook of Constraint Programming. Elsevier, Amsterdam (2006)
Pini, M.S., Rossi, F., Venable, K.B., Dechter, R.: Robust solutions in unstable optimization problems. In: Proc. Recent Advances in Constraints, LNAI. Springer, New York (2009)
Rossi, F., Van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, Amsterdam (2006)
Ruttkay, Z.: Fuzzy constraint satisfaction. In: Proceedings 1st IEEE Conference on Evolutionary Computing, pp. 542–547. Orlando (1994)
Zivan, R., Shapen, U., Meisels, A.: Meeting scheduling problem (MSP). Available at http://www.cs.st-andrews.ac.uk/~ianm/CSPLib/prob/prob046/index.html (2010)
Wilson, N., Grimes, D., Freuder, E.C.: A cost-based model and algorithms for interleaving solving and elicitation of CSPS. In: Proc. CP’07, volume 4741 of LNCS, pp. 666–680. Springer, New York (2007)
Yorke-Smith, N., Gervet, C.: Certainty closure: A framework for reliable constraint reasoning with uncertainty. In: Proc. CP’03, volume 2833 of LNCS, pp. 769–783. Springer, New York (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gelain, M., Pini, M.S., Rossi, F. et al. Interval-valued soft constraint problems. Ann Math Artif Intell 58, 261–298 (2010). https://doi.org/10.1007/s10472-010-9203-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-010-9203-0