Reducing Symmetry in a Combinatorial Design Problem
Proceedings of CP-AI-OR'01, pp. 351-359, April 2001.
Barbara M Smith
Abstract
A combinatorial design problem is considered which can be modelled as a
constraint satisfaction problem in several different ways. The models all
have a large number of symmetries which cause difficulties when searching
for solutions. Different approaches to reducing the symmetry are discussed:
remodelling the problem; adding constraints to the model at the outset; and
adding constraints during search to prevent symmetric assignments being
explored on backtracking. The most successful strategy for the problem of
this paper employs a complex model with less inherent symmetry than the
others, combined with symmetry breaking during search.