Decomposition strategies for configuration problems

Content Provider	Scilit
Author	Magro, Diego Torasso, Pietro
Copyright Year	2003
Description	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.
Related Links	https://www.cambridge.org/core/services/aop-cambridge-core/content/view/9E5A4BC687107AB858FC9C66458C8487/S0890060403171053a.pdf/div-class-title-decomposition-strategies-for-configuration-problems-div.pdf
Ending Page	73
Page Count	23
Starting Page	51
ISSN	08900604
e-ISSN	14691760
DOI	10.1017/s0890060403171053
Journal	Artificial Intelligence for Engineering Design, Analysis and Manufacturing
Issue Number	1
Volume Number	17
Language	English
Publisher	Cambridge University Press (CUP)
Publisher Date	2003-02-01
Access Restriction	Open
Subject Keyword	Artificial Intelligence for Engineering Design, Analysis and Manufacturing Software Engineering Configuration Problem Performance of the Configurator
Content Type	Text
Resource Type	Article
Subject	Industrial and Manufacturing Engineering Artificial Intelligence