Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-28T22:34:22.239Z Has data issue: false hasContentIssue false
  • English
  • Français

Preference programming: Advanced problem solving for configuration

Published online by Cambridge University Press:  07 August 2003

ULRICH JUNKER  and
DANIEL MAILHARRO
ULRICH JUNKER
Affiliation:
ILOG SA, 06560 Valbonne, France
DANIEL MAILHARRO
Affiliation:
ILOG SA, BP 85, F-94253 Gentilly Cedex, France
Get access Rights & Permissions [Opens in a new window]

Abstract

Configuration problems often involve large product catalogs, and the given user requests can be met by many different kinds of parts from this catalog. Hence, configuration problems are often weakly constrained and have many solutions. However, many of those solutions may be discarded by the user as long as more interesting solutions are possible. The user often prefers certain choices to others (e.g., a red color for a car to a blue color) or prefers solutions that minimize or maximize certain criteria such as price and quality. In order to provide satisfactory solutions, a configurator needs to address user preferences and user wishes. Another important problem is to provide high-level features to control different reasoning tasks such as solution search, explanation, consistency checking, and reconfiguration. We address those problems by introducing a preference programming system that provides a new paradigm for expressing user preferences and user wishes and provides search strategies in a declarative and unified way, such that they can be embedded in a constraint and rule language. The preference programming approach is completely open and dynamic. In fact, preferences can be assembled from different sources such as business rules, databases, annotations of the object model, or user input. An advanced topic is to elicit preferences from user interactions, especially from explanations of why a user rejects proposed choices. Our preference programming system has successfully been used in different configuration domains such as loan configuration, service configuration, and other problems.

Type
Research Article
Information
AI EDAM , Volume 17 , Issue 1 , February 2003 , pp. 13 - 29
Copyright
© 2003 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

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(3), 199–240.Google Scholar
Boutilier, C., Brafman, R., Geib, C., & Poole, D. (1997). A constraint-based approach to preference elicitation and decision making. In Working Papers of the AAAI Spring Symposium on Qualitative Preferences in Deliberation and Practical Reasoning (Doyle, J. & Thomason, R.H., Eds.), pp. 19–28. Menlo Park, CA: AAAI Press.
Brewka, G. (1989). Preferred subtheories: An extended logical theory for default reasoning. Proc. Eleventh Int. Joint Conf. Artificial Intelligence (Sridharan, N.S., Ed.), pp. 1043–1048. San Mateo, CA: Morgan Kaufmann.
Brewka, G. (1994). Reasoning about priorities in default logic. Proc. Twelfth National Conf. Artificial Intelligence (AAAI), pp. 940–945. Menlo Park, CA: AAAI Press.
Delgrande, J.P. & Schaub, T. (2000). Expressing preferences in default logic. Artificial Intelligence 123(1–2), 41–87.Google Scholar
Domshlak, C., Brafman, R.I., & Shimony, S.E. (2001). Preference-based configuration of web page content. Proc. Seventeenth Int. Joint Conf. Artificial Intelligence, pp. 1451–1456. San Francisco, CA: Morgan Kaufmann.
Doyle, J. (2002). Preferences: Some problems and prospects. In AAAI-02 Workshop on Preferences in AI and CP: Symbolic Approaches. Menlo Park: AAAI Press.
Ehrgott, M. (1997). A characterization of lexicographic max-ordering solutions. Methods of Multicriteria Decision Theory: Proceedings of the 6th Workshop of the DGOR Working-Group Multicriteria Optimization and Decision Theory, pp. 193–202. Egelsbach, Germany: Häsel-Hohenhausen.
Freuder, E.C. (1991). Eliminating interchangeable values in constraint satisfaction problems. Proc. Ninth National Conf. Artificial Intelligence (AAAI) (Dean, K. & McKeown, T.L., Eds.), pp. 227–233. Cambridge, MA: MIT Press.
Haselböck, A. & Stumptner, M. (1993). An integrated approach for modelling complex configuration domains. 13th Int. Conf. Expert Systems, AI, and Natural Language, Avignon, France, pp. 625–634.
ILOG. (2002). ILOG JConfigurator V2.0: Product information. Available on-line at www.ilog.com/products/jconfigurator/.
Junker, U. (1993). Dynamic generation of assumptions and preferences. In Actes des Vièmes Journées du Laboratoire d'Informatique de Paris Nord (Bidoit, N., Ed.), pp. 1–21. Paris: Villetaneuse.
Junker, U. (1997). A cumulative-model semantics for dynamic preferences on assumptions. Proc. Fifteenth Int. Joint Conf. Artificial Intelligence, pp. 162–167. San Francisco, CA: Morgan Kaufmann.
Junker, U. (2000). Preference-based search for scheduling. Proc. Seventeenth National Conf. Artificial Intelligence (AAAI), pp. 904–909. Menlo Park, CA: AAAI Press.
Junker, U. (2002). Preference-based search and multi-criteria optimization. Proc. Eighteenth National Conf. Artificial Intelligence (AAAI), pp. 34–40. Menlo Park, CA: AAAI Press.
Mailharro, D. (1998). A classification and constraint based framework for configuration. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12(4), 383–397.Google Scholar
Mittal, S. & Frayman, F. (1989). Towards a generic model of configuration tasks. Proc. Eleventh Int. Joint Conf. Artificial Intelligence (Sridharan, N.S., Ed.), pp. 1395–1401. San Mateo, CA: Morgan Kaufmann.
Poole, D. (1988). A logical framework for default reasoning. Artificial Intelligence 36(1), 27–47.Google Scholar
Puget, J.-F. (1992). Object-oriented constraint programming. Artificial Intelligence, Expert Systems, Natural Language: Twelfth Int. Conf., pp. 129–138, Avignon, France.
SABRE. (2002). Sabre trip shopping: Product information. Available on-line at www.sabretravelnetwork.com/products_and_services/travel_agencies/s1_000999.htm.
Soininen, T., Niemelä, I., Tiihonen, J., & Sulonen, R. (2000). Unified configuration knowledge representation using weight constraint rules. ECAI-2000 Workshop on Configuration, Berlin, pp. 79–84.
Torrens, M. & Faltings, B. (2002). Using soft CSPs for approximating Pareto-optimal solutions sets. AAAI-02 Workshop on Preferences in AI and CP: Symbolic Approaches. Menlo Park, CA: AAAI Press.
van Hentenryck, P. & Puget, J.-F. (2000). Search and strategies in OPL. ACMTCL: ACM Transactions on Computational Logic 1.