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. A recently observed phenomenon is the negative effect of symmetry breaking constraints on local search performance. The reasons for this are poorly understood, and we attempt to shed light on the phenomenon by testing three conjectures: that the constraints create deep new local optima; that they can reduce the relative size of the basins of attraction of global optima; and that complex local search heuristics reduce their negative effects.
Symmetry breaking and local search spaces / Prestwich, S.; Roli, Andrea. - STAMPA. - 3524:(2005), pp. 273-287. (Intervento presentato al convegno CP-AI-OR 2005, International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems tenutosi a Prague, Czech Republic nel May 29 - June 1, 2005).
Symmetry breaking and local search spaces
ROLI, ANDREA
2005
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 and models. A recently observed phenomenon is the negative effect of symmetry breaking constraints on local search performance. The reasons for this are poorly understood, and we attempt to shed light on the phenomenon by testing three conjectures: that the constraints create deep new local optima; that they can reduce the relative size of the basins of attraction of global optima; and that complex local search heuristics reduce their negative effects.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.