Fast Canonical Configuration Generation and Filtering

Contents

Constraint based configuration challenges symmetry elimination methods known to the constraint solving community by introducing dynamics. We present here a significant improvement of an algorithm for generating canonical configurations. The new version fully exploits the incremental generation of canonical solutions both at the level of the canonicity test and in the tree ordering function, which turns the cost of canonicity testing down from O(Nlog(N)) to O(N). Filtering additionally provides the possibility to proactively discard failure situations. Experimental results provide evidence of the significance of this approach, on test problems and known benchmarks.