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 non-interacting 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 FPC language, a KL-One like representation formalism augmented with constraints for expressing complex inter-role 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 which 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 the parts that are not related to 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 non-interacting 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.
Decomposition Strategies for Configuration Problems
MAGRO, Diego;TORASSO, Pietro
2003-01-01
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 non-interacting 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 FPC language, a KL-One like representation formalism augmented with constraints for expressing complex inter-role 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 which 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 the parts that are not related to 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 non-interacting 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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
