Pruning Isomorphic Structural Sub-problems in Configuration
<|reference_start|>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.<|reference_end|>
@article{grandcolas2003pruning,
    title={Pruning Isomorphic Structural Sub-problems in Configuration},
    author={Stephane Grandcolas and Laurent Henocque and Nicolas Prcovic},
    journal={arXiv preprint arXiv:cs/0306135},
    year={2003},
    number={LSIS-2003-004},
    archivePrefix={arXiv},
    eprint={cs/0306135},
    primaryClass={cs.AI}
}