Computer Science – Artificial Intelligence
Scientific paper
2003-06-27
Computer Science
Artificial Intelligence
This research report contains the proofs and full details missing from the short paper "A Canonicity Test for Configuration" i
Scientific paper
Configuring consists in simulating the realization of a complex product from a catalog of component parts, using known relations between types, and picking values for object attributes. This highly combinatorial problem in the field of constraint programming has been addressed with a variety of approaches since the foundation system R1(McDermott82). An inherent difficulty in solving configuration problems is the existence of many isomorphisms among interpretations. We describe a formalism independent approach to improve the detection of isomorphisms by configurators, which does not require to adapt the problem model. To achieve this, we exploit the properties of a characteristic subset of configuration problems, called the structural sub-problem, which canonical solutions can be produced or tested at a limited cost. In this paper we present an algorithm for testing the canonicity of configurations, that can be added as a symmetry breaking constraint to any configurator. The cost and efficiency of this canonicity test are given.
Grandcolas Stephane
Henocque Laurent
Prcovic Nicolas
No associations
LandOfFree
Pruning Isomorphic Structural Sub-problems in Configuration does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Pruning Isomorphic Structural Sub-problems in Configuration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pruning Isomorphic Structural Sub-problems in Configuration will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-335193