Reducing Symmetry in a Combinatorial Design Problem
Research Report 2001.01, School of Computing, University of Leeds,
January 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.
Back to "Barbara Smith
- Papers on Constraint Programming"