Abstract
A depth-first search algorithm can be used to find optimal solutions of a Constraint Satisfaction Problem (CSP) with respect to a set of conditional preferences statements (e.g., a CP-net). This involves checking at each leaf node if the corresponding solution of the CSP is dominated by any of the optimal solutions found so far; if not, then we add this solution to the set of optimal solutions. This kind of algorithm can clearly be computationally expensive if the number of solutions is large. At a node N of the search tree, with associated assignment b to a subset of the variables B, it may happen that, for some previously found solution α, either (a) α dominates all extensions of b; or (b) α does not dominate any extension of a. The algorithm can be significantly improved if we can find sufficient conditions for (a) and (b) that can be efficiently checked. In case (a), we can backtrack since we need not continue the search below N; in case (b), α does not need to be considered in any node below the current node N. We derive a sufficient condition for (b), and three sufficient conditions for (a). Our experimental testing indicates that this can make a major difference to the efficiency of constrained optimisation for conditional preference theories including CP-nets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bessiere, C.: Constraint propagation. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming. Elsevier, Amsterdam (2006)
Bienvenu, M., Lang, J., Wilson, N.: From preference logics to preference languages, and back. In: Proc. KR 2010 (2010)
Boutilier, C., Brafman, R., Hoos, H., Poole, D.: Reasoning with conditional ceteris paribus preference statements. In: Proceedings of UAI 1999, pp. 71–80 (1999)
Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H., Poole, D.: CP-nets: A tool for reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research 21, 135–191 (2004)
Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H., Poole, D.: Preference-based constrained optimization with CP-nets. Computational Intelligence 20(2), 137–157 (2004)
Brafman, R., Domshlak, C., Shimony, E.: On graphical modeling of preference and importance. Journal of Artificial Intelligence Research 25, 389–424 (2006)
Fahle, T., Schamberger, S., Sellmann, M.: Symmetry breaking. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 93–107. Springer, Heidelberg (2001)
Goldsmith, J., Lang, J., Truszczyński, M., Wilson, N.: The computational complexity of dominance and consistency in CP-nets. Journal of Artificial Intelligence Research 33, 403–432 (2008)
McGeachie, M., Doyle, J.: Utility functions for ceteris paribus preferences. Computational Intelligence 20(2), 158–217 (2004)
Santhanam, G., Basu, S., Honavar, V.: Dominance testing via model checking. In: Proc. AAAI 2010 (2010)
Trabelsi, W., Wilson, N., Bridge, D., Ricci, F.: Comparing approaches to preference dominance for conversational recommender systems. In: Proc. ICTAI, pp. 113–118 (2010)
Wilson, N.: Consistency and constrained optimisation for conditional preferences. In: Proceedings of ECAI 2004, pp. 888–892 (2004)
Wilson, N.: Extending CP-nets with stronger conditional preference statements. In: Proceedings of AAAI 2004, pp. 735–741 (2004)
Wilson, N.: An efficient upper approximation for conditional preference. In: Proceedings of ECAI 2006, pp. 472–476 (2006)
Wilson, N.: Computational techniques for a simple theory of conditional preferences. Artificial Intelligence (in press, 2011), doi:10.1016/j.artint.2010.11.018
Wilson, N.: Efficient inference for expressive comparative preference languages. In: Proceedings of IJCAI 2009, pp. 961–966 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wilson, N., Trabelsi, W. (2011). Pruning Rules for Constrained Optimisation for Conditional Preferences. In: Lee, J. (eds) Principles and Practice of Constraint Programming – CP 2011. CP 2011. Lecture Notes in Computer Science, vol 6876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23786-7_60
Download citation
DOI: https://doi.org/10.1007/978-3-642-23786-7_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23785-0
Online ISBN: 978-3-642-23786-7
eBook Packages: Computer ScienceComputer Science (R0)