×

Lexicographically-ordered constraint satisfaction problems. (English) Zbl 1191.68632

Summary: We describe a simple CSP formalism for handling multi-attribute preference problems with hard constraints, one that combines hard constraints and preferences so the two are easily distinguished conceptually and for purposes of problem solving. Preferences are represented as a lexicographic order over complete assignments based on variable importance and rankings of values in each domain. Feasibility constraints are treated in the usual manner. Since the preference representation is ordinal in character, these problems can be solved with algorithms that do not require evaluations to be represented explicitly. This includes ordinary CSP algorithms, although these cannot stop searching until all solutions have been checked, with the important exception of heuristics that follow the preference order (lexical variable and value ordering).
We describe relations between lexicographic CSPs and more general soft constraint formalisms and show how a full lexicographic ordering can be expressed in the latter. We discuss relations with (T)CP-nets, highlighting the advantages of the present formulation, and we discuss the use of lexicographic ordering in multiobjective optimisation. We also consider strengths and limitations of this form of representation with respect to expressiveness and usability. We then show how the simple structure of lexicographic CSPs can support specialised algorithms: a branch and bound algorithm with an implicit cost function, and an iterative algorithm that obtains optimal values for successive variables in the importance ordering, both of which can be combined with appropriate variable ordering heuristics to improve performance. We show experimentally that with these procedures a variety of problems can be solved efficiently, including some for which the basic lexically ordered search is infeasible in practice.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W05 Nonnumerical algorithms

Software:

SOFT; CP-nets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arrow, K. J., & Raynaud, H. (1986). Social choice and multicriterion decision-making. MIT. · Zbl 0602.90001
[2] Bistarelli, S., Montanari, U., & Rossi, F. (1997). Semiring-based constraint solving and optimization. Journal on ACM, 44, 201–236. · Zbl 0890.68032 · doi:10.1145/256303.256306
[3] Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., & Fargier, H. (1999). Semiring-based CSPs and valued CSPs: Frameworks, properties and comparison. Constraints, 4, 199–240. · Zbl 0946.68143 · doi:10.1023/A:1026441215081
[4] Borcherding, K., Eppel, T., & von Winterfeldt, D. (1991). Comparison of weighting judgments in multiattribute utility measurement. Management Science, 37, 1603–1619. · Zbl 0729.91012 · doi:10.1287/mnsc.37.12.1603
[5] Borning, A., Freeman-Benson, B., & Wilson, M. (1992) Constraint hierarchies. LISP and Symbolic Computation, 5, 223–270. · doi:10.1007/BF01807506
[6] Boutilier, C., Brafman, R. I., Hoos, H. H., & Poole, D. (1999). Reasoning with conditional ceteris paribus preference statements. In Proc. fifteenth annual conference on uncertainty in artificial intelligence (pp. 71–80). Morgan Kaufmann. · Zbl 1080.68685
[7] Boutilier, C., Brafman, R. I., Domshlak, C., Hoos, H., & Poole, D. (2004a). CP-nets: A tool for representing and reasoning with ceteris paribus preference statements. Journal of Artificial Intelligence Research, 21, 135–191. · Zbl 1080.68685
[8] Boutilier, C., Brafman, R. I., Domshlak, C., Hoos, H., & Poole, D. (2004b). Preference-based constrained optimization with CP-nets. Computational Intelligence, Special Issue on Preferences, 20, 137–157. · Zbl 1080.68685
[9] Brafman, R. I., & Domshlak, C. (2002). Introducing variable importance tradeoffs into CP-nets. In Proc. eighteenth annual conference on uncertainty in artificial intelligence (pp. 69–76). AAAI Press.
[10] Brafman, R. I., Domshlak, C., & Shimony, E. (2006). Graphical modeling of preference and importance. Journal of Artificial Intelligence Research, 25, 389–424. · Zbl 1182.68325
[11] Brewka, G. (1989). Preferred subtheories: An extended logical framework for default reasoning. In Proc. eleventh international joint conference on artificial intelligence (pp. 1043–1048). Morgan Kaufmann. · Zbl 0713.68053
[12] Chankong, V., & Haimes, Y. Y. (1983). Multiobjective decision making. Dover. · Zbl 0525.90085
[13] Cheeseman, P., Kanefsky, B., & Taylor, W. M. (1991). Where the really hard problems are. In Proc. twelth international joint conference on artificial intelligence (pp. 331–337). Morgan Kaufmann. · Zbl 0747.68064
[14] Domshlak, C., & Brafman, R. I. (2002). CP-nets - reasoning and consistency testing. In Proc. eighth conference on principles of knowledge representation and reasoning (pp. 121–132). Morgan Kaufmann.
[15] Doyle, J., & Thomason, R. H. (1999). Background to qualitative decision theory. Artificial Intelligence Magazine, 20, 55–68.
[16] Ehrgott, M. (2005). Multicriteria Optimization. 2nd edition. Springer. · Zbl 1132.90001
[17] Ehrgott, M., & Wiecek, M. M. (2005). Multiobjective programming. In J. Figueira, S. Greco, & M. Ehrgott (eds.), Multiple criteria decision analysis. State of the art surveys (pp. 667–722). Springer. · Zbl 1072.90031
[18] Fargier, H., Lang, J., & Schiex, T. (1993). Selecting preferred solutions in fuzzy constraint satisfaction problems. In Proc. first European conference on fuzzy and intelligent technologies - EUFIT’93 (pp. 1128–1134). Augustinus Buchhandlung.
[19] Fishburn, P. C. (1970). Utility theory for decision making. Wiley. · Zbl 0213.46202
[20] Fishburn, P. C. (1974). Lexicographic orders, utilities and decision rules: A survey. Management Science, 20, 1442–1471 · Zbl 0311.90007 · doi:10.1287/mnsc.20.11.1442
[21] Fishburn, P. C. (1975). Axioms for lexicographic preferences. Review of Economic Studies, 42, 415–419. · Zbl 0326.90005 · doi:10.2307/2296854
[22] Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., & Walsh, T. (2002). Global constraints for lexicographic orderings. In P. V. Hentenryck (ed.), Principles and practice of constraint programming - CP2002, LNCS (vol. 2470, pp. 93–108). Springer.
[23] Freuder, E. C., Wallace, R. J., & Heffernan, R. (2003). Ordinal constraint satisfaction. In Fifth international workshop on soft constraints - SOFT’03. · Zbl 1102.90379
[24] Frost, D., & Dechter, R. (1995). Look-ahead value ordering for constraint satisfaction problems. In Proc. fourteenth international joint conference on artificial intelligence (pp. 572–578). Morgan Kaufmann.
[25] Gavanelli, M. (2002). An algorithm for multi-criteria optimization in CSPs. In F. van Harmelen (ed.), Fifteenth European conference on artificial intelligence-ECAI 2002 (pp. 136–140). IOS Press.
[26] Goldsmith, J., Lang, J., Truszczynski, M., & Wilson, N. (2005). The computational complexity of dominance and consistency in CP-nets. In Proc. nineteenth international joint conference on artificial intelligence (pp. 144–149). · Zbl 1182.68089
[27] Haralick, R. M., & Elliott, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14, 263–313. · doi:10.1016/0004-3702(80)90051-X
[28] Joseph, R. R., Chan, P., Hiroux, M., & Weil, G. (2007). Decision-support with preference constraints. European Journal of Operational Research, 177, 1469–1494. · Zbl 1109.90071 · doi:10.1016/j.ejor.2005.04.016
[29] Junker, U. (2002). Preference-based search and multi-criteria optimization. In Proc. eighteenth national conference on artificial intelligence (pp. 34–40). AAAI Press.
[30] Junker, U. (2004). Preference-based search and multi-criteria optimization. Annals of Operation Research, 130, 75–115 · Zbl 1156.90381 · doi:10.1023/B:ANOR.0000032571.68051.fe
[31] Junker, U. (2008). Preference-based problem solving for constraint programming. In F. Fages, F. Rossi, & S. Soliman (eds.), Recent advances in constraints: 12th annual ERCIM international workshop on constraint solving and constraint logic programming - CSCLP 2007. LNAI (vol. 5129, pp. 109–126). Revised selected papers. Springer.
[32] Keeney, R. L., & Raiffa, H. (1993). Decisions with multiple objectives. Cambridge. · Zbl 0488.90001
[33] Korhonen, M. (2005). Interactive methods. In J. Figueira, S. Greco, & M. Ehrgott (eds.), Multiple criteria decision analysis. State of the art surveys (pp. 641–665). Springer. · Zbl 1072.90537
[34] Larichev, O. I. (1984). Psychological validation of decision methods. Journal of Applied Systems Analysis, 11, 37–46.
[35] Laumanns, M., Thiele, L., & Zitzler, E. (2006). An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal on Operational Research, 169, 932–942. · Zbl 1079.90122 · doi:10.1016/j.ejor.2004.08.029
[36] Lecoutre, C., Boussemart, F., & Hemery, F. (2004). Backjump-based techniques versus conflict-directed heuristics. In Proc. sixteenth international conference on tools with artificial intelligence-ICTAI’04 (pp. 549–557). IEEE Press.
[37] Luce, R. D., & Suppes, P. (1965). Preference, utility and subjective probability. In R. D. Luce, R. R. Bush, & E. Galanter (eds.), Handbook of mathematical psychology (vol. 3, pp. 249–410). Wiley.
[38] Majumdar, T. (1966). The measurement of utility. Macmillan.
[39] Olson, D. L., Moshkovich, H. M., Schellenberger, R., & Mechitov, A. I. (1995). Consistency and accuracy in decision aids: Experiments with four multiattribute systems. Decision Science, 26, 723–746. · doi:10.1111/j.1540-5915.1995.tb01573.x
[40] Payne, J. W., Bettman, J. R., & Johnson, E. J. (1993). The adaptive decision maker. Cambridge.
[41] Plott, C. R., Little, J. T., & Parks, R. P. (1975). Individual choices when objects have ”ordinal” properties. Review of Economic Studies, 42, 403–413. · Zbl 0326.90004 · doi:10.2307/2296853
[42] Saaty, T. L. (2005). The analytic hierarchy and analytic network processes for the measurement of intangible criteria and for decision-making. In J. Figueira, S. Greco, & M. Ehrgott (Eds.), Multiple criteria decision analysis (pp. 345–407). Springer. · Zbl 1072.90019
[43] Sabin, D., & Freuder, E. (1994). Contradicting conventional wisdom in constraint satisfaction. In Proc. eleventh European conference on artificial intelligence (pp. 125–129). Wiley.
[44] Smith, B. M., & Grant, S. A. (1998). Trying harder to fail first. In Proc. thirteenth European conference on artificial intelligence–ECAI’98 (pp. 249–253). Wiley.
[45] Schiex, T., Fargier, H., & Verfaillie, G. (1995). Valued constraint satisfaction problems: Hard and easy problems. In Proc. fourteenth international joint conference on artificial intelligence (pp. 631–637). Morgan Kaufmann.
[46] Wallace, R. J., & Wilson, N. (2006). Conditional lexicographic orders in constraint satisfaction problems. In J. C. Beck, & B. M. Smith (eds.), Proc. third international conference on integration of AI and OR techniques in constraint programming - CPAIOR 2006. LNCS (no. 3990, pp. 258–272). Berlin: Springer. · Zbl 1177.68194
[47] Wilson, N. (2004a). Consistency and constrained optimisation for conditional preferences. In Proc. sixteenth European conference on artificial intelligence (pp. 888–892). IOS Press.
[48] Wilson, N. (2004b). Extending CP-nets with stronger conditional preference statements. In Proc. nineteenth national conference on artificial intelligence (pp. 735–741). AAAI/MIT.
[49] Wilson, N. (2006). An efficient upper approximation for conditional preference. In Proc. seventeenth European conference on artificial intelligence (pp. 472–476). IOS Press.
[50] Wallace, R. J., & Wilson, N. (2009). Conditional lexicographic orders in constraint satisfaction problems. Annals of Operations Research special issue entitled ”Constraint Programming, Artificial Intelligence and Operations Research”. · Zbl 1184.68478
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.