| On 2007-03-07 at 11:00:00 (Brussels Time) |
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
-
S.Prestwich and A.Roli. (2005)
Symmetry breaking and local search spaces.
In
LNCS Vol.3524. Springer.
