Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-28T22:18:40.113Z Has data issue: false hasContentIssue false
  • English
  • Français

Decomposition strategies for configuration problems

Published online by Cambridge University Press:  07 August 2003

DIEGO MAGRO  and
PIETRO TORASSO
DIEGO MAGRO
Affiliation:
Dipartimento di Informatica, Università di Torino, 10149 Torino, Italy
PIETRO TORASSO
Affiliation:
Dipartimento di Informatica, Università di Torino, 10149 Torino, Italy
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper introduces and discusses the notion of decomposition of a configuration problem within the framework of a structured logical approach. The paper describes under which conditions a given configuration problem can be decomposed into a set of noninteracting subproblems and how to exploit such a decomposition, both for improving the performance of the configurator and for supporting interactive configuration. Different kinds of decomposition are considered, but all of them exploit, as much as possible, the explicit representation of the partonomic relations in the language, a KL-One like representation formalism augmented with constraints for expressing complex interrole relations. The paper introduces a notion of boundness among constraints, which is used for formally specifying different types of decomposition. One decomposition strategy aims at singling out the components and subcomponents that are directly related to the constraints put by the user's requirements; the configurator exploits such decomposition by first configuring that portion of the product and then configuring the parts that are not related to the user's requirements. Another decomposition strategy verifies whether the set of constraints for the product to be configured can be split into a set of noninteracting problems. In such a case the configurator solves the configuration problem by splitting the whole search space into a set of smaller search spaces. Different combinations of these two decomposition techniques are considered, and the impact of the decomposition strategies on the performance of the configurator is evaluated via a set of experiments using the configuration of computer systems as a test bed. The results of the experiments show a significant reduction of the computational effort (both in terms of number of backtrackings and in CPU time) when decomposition strategies are used.

Type
Research Article
Information
AI EDAM , Volume 17 , Issue 1 , February 2003 , pp. 51 - 73
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

Felfernig, A., Friedrich, G.E., & Jannach, D. (2000). UML as domain specific language for the construction of knowledge-based configuration systems. International Journal of Software Engineering and Knowledge Engineering 10(4), 449–469.Google Scholar
Fleischanderl, G., Friedrich, G.E., Haselböck, A., Schreiner, H., & Stumptner, M. (1998). Configuring large systems using generative constraint satisfaction. IEEE Intelligent Systems 13, 59–68.Google Scholar
Fleischanderl, G. & Haselböck, A. (1996). Thoughts on partitioning large-scale configuration problems. AAAI 1996 Fall Symposium Series, pp. 1–10.
Friedrich, G. & Stumptner, M. (1999). Consistency-based configuration. AAAI-99, Workshop on Configuration.
Gerstl, P. & Pribbenow, S. (1995). Midwinters, end games, and body parts: A classification of part–whole relations. International Journal of Human–Computer Studies 43, 865–889.Google Scholar
Gottlob, G., Leone, N., & Scarcello, F. (2000). A comparison of structural CSP decomposition methods. Artificial Intelligence 124, 243–282.Google Scholar
Magro, D. & Torasso, P. (2000). Description and configuration of complex technical products in a virtual store. Proc. ECAI 2000 Configuration Workshop, pp. 50–55.
Magro, D. & Torasso, P. (2001a). Interactive configuration capability in a sale support system: Laziness and focusing mechanisms. Proc. IJCAI-01 Configuration Workshop, pp. 57–63.
Magro, D. & Torasso, P. (2001b). Supporting product configuration in a virtual store. LNAI 2175, 176–188.Google Scholar
Magro, D., Torasso, P., & Anselma, L. (2002). Problem decomposition in configuration. Proc. ECAI 2002 Configuration Workshop, pp. 50–55.
Mailharro, D. (1998). A classification and constraint-based framework for configuration. Artificial Intelligence in Engineering Design, Analysis and Manufacturing 12(4), 383–397.Google Scholar
McGuinness, D. (2002). Configuration. In The Description Logic Handbook. Theory, Implementation, and Applications (Baader, F., McGuinness, D., Nardi, D. & Patel–Schneider, P., Eds.). Cambridge: Cambridge University Press.
McGuinness, D.L. & Wright, J.R. (1998). An industrial-strength description logic–based configurator platform. IEEE Intelligent Systems 13, 69–77.Google Scholar
Mittal, S. & Falkenhainer, B. (1990). Dynamic constraint satisfaction problems. Proc. AAAI 90, pp. 25–32.
Mittal, S. & Frayman, F. (1989). Towards a generic model of configuration tasks. Proc. IJCAI-89, pp. 1395–1401.
Park, T.J. & Gelder, A.V. (2000). Partitioning methods for satisfiability testing on large formulas. Information and Computation 162, 179–184.Google Scholar
Sabin, D. & Freuder, E. (1996). Configuration as composite constraint satisfaction. Proc. Artificial Intelligence and Manufacturing Research Planning Workshop, pp. 153–161.
Soininen, T. (2000). An approach to knowledge representation and reasoning for product configuration tasks. PhD thesis. Espoo, Finland: Helsinki University of Technology. Available on-line at www.soberit.hut.fi/pdmg/papers/soin00App.pdf.
Soininen, T. & Gelle, E. (1999). Dynamic constraint satisfaction in configuration. Configuration Papers from the AAAI Workshop, pp. 95–100. AAAI Technical Report WS-99-05.
Soininen, T., Niemelä, I., Tiihonen, J., & Sulonen, R. (2000). Unified configuration knowledge representation using weight constraint rules. Proc. ECAI 2000 Configuration Workshop, pp. 79–84.
Soininen, T., Tiihonen, J., Männistö, T., & Sulonen, R. (1998). Towards a general ontology of configuration. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12(4), 383–397.Google Scholar
Stumptner, M. & Haselböck, A. (1993). A generative constraint formalism for configuration problems. LNAI 728, 302–313.Google Scholar
Veron, M. & Aldanondo, M. (2000). Yet another approach to CCSP for configuration problems. Proc. ECAI 2000 Configuration Workshop, pp. 59–62.
Weida, R. (1996). Closed terminology in description logics. Proc. AAAI-96, Vol. 1, pp. 592–599.