Pruning Isomorphic Structural Sub-problems in Configuration
  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.
