Negative Effects of Modeling Techniques on Search Performance

Symmetries occur in many combinatorial problems, and a great deal of research has been done on symmetry breaking techniques for backtrack search. However, few results have been reported on the use of symmetry breaking with local search. On four classes of problem we find that adding symmetry breaking constraints to a model impairs local search performance, in terms of both execution time and search steps. We also find that implied constraints can impair backtrack search performance. These results show that modeling techniques and search heuristics should be combined with caution. They also motivate a novel modeling technique for local search: removing constraints to add new symmetries.