Pruning Isomorphic Structural Sub-problems in Configuration
| dc.creator | Grandcolas, Stephane | |
| dc.creator | Henocque, Laurent | |
| dc.creator | Prcovic, Nicolas | |
| dc.date | 2003-06-27 | |
| dc.date.accessioned | 2026-07-07T03:19:59Z | |
| dc.date.available | 2026-07-07T03:19:59Z | |
| dc.description | 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. | |
| dc.description | This research report contains the proofs and full details missing from the short paper "A Canonicity Test for Configuration" in proceedings of conference CP'03 | |
| dc.identifier | https://arxiv.org/abs/cs/0306135 | |
| dc.identifier | http://arxiv.org/abs/cs/0306135 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31678 | |
| dc.subject | Artificial Intelligence | |
| dc.subject | I.2.3; I.2.4; I.2.8; F.4.1 | |
| dc.title | Pruning Isomorphic Structural Sub-problems in Configuration | |
| dc.type | text |