Back to the program.
Symmetry-breaking and local search
Andrea Roli
DEIS
Alma Mater Studiorum - Università di Bologna
Campus of Cesena
andrea.roli@unibo.it

Abstract

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. 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. In this talk, we discuss the current conjectures on this phenomenon and propose a new hypothesis composed of two statements: (i) Symmetry-breaking constraints can reduce the relative size of the basins of attraction of global optima, where basins are relative to deterministic best improvement. 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 dampen this negative effect, as they are equipped with advanced diversification strategies. This approach can also be generalized to study other related phenomena, such as the effect of redundant constraints or constraint-based neigborhoods.

Keywords

local search, symmetry-breaking constraints, basins of attraction

References

  1. S.Prestwich and A.Roli. (2005) Symmetry breaking and local search spaces. In LNCS Vol.3524. Springer.