Symmetry-breaking and local search

The effects of combining search and modelling techniques can be complex and unpredictable, so guidelines are very important for the design and development of effective and robust solvers and models. This is an issue not only for exact solvers, but also for approximate techniques, such as local search. A recently observed phenomenon is the negative effect of symmetry breaking constraints on local search performance. The reasons for this are poorly understood and they are likely to be found in the structure of the search space, mainly in the reachability of solutions. With this work, we attempt to shed light on the phenomenon by testing the following conjecture, composed of two statements: (i) Symmetry-breaking constraints can reduce the relative size of the basins of attraction of global optima (basins are defined upon the application of a best improvement local search). Since most local search strategies incorporate a greedy component like best improvement, they should be affected by this reduction of global optima basins of attraction; therefore, (ii) we should observe a positive correlation between size of global optima basins of attraction and algorithm effectiveness. Moreover, we should observe that complex local search heuristics can dampen this negative effect, as they are equipped with advanced diversification strategies. This conjecture can provide one of the main reasons for the negative effect of symmetry-breaking constraints on local search. In this work, we report and discuss a series of experiments that support this conjecture by showing that (i) in most of the instances analyzed the total basin of attraction of global optima in the model with symmetry-breaking constraints is reduced by a factor that is higher than the search space reduction factor ascribed to the imposition of such constraints; moreover, results show that (ii) local search effectiveness is positively correlated with the size of global optima basins of attraction.