Symmetry-Breaking and Local Search: A Case Study

Symmetry-breaking has been proved to be very effective when combined with complete solvers. Conversely, it has been conjectured that the use of symmetry-breaking constraints has negative effect on local search-based solvers. This work presents an attempt to model the effect of symmetry-breaking on the search landscape explored by local search. The results, on the one hand, exclude that symmetry-breaking constraints negatively affect the topology of the search space. On the other hand, they strongly suggest that symmetry-breaking perturbs the configuration of local and global optima basins of attraction, making global optima more difficult to be reached.