IMDEA Software

IMDEA initiative

Home > Events > Software Seminar Series > 2008 > Symmetry Detection and Symmetry Breaking

Maria Garcia de la Banda

Tuesday, September 23, 2008

11:00am Meeting room 302 (Mountain View), level 3

Maria Garcia de la Banda, Associate Professor, Monash University, Australia

Symmetry Detection and Symmetry Breaking

Abstract:

Many constraint problems have a considerable number of symmetries. Detecting and breaking these symmetries is a very active research area. This is due to the potential speedups one can gain by avoiding the exploration of parts of the search tree that are symmetric to others already explored. In this talk I will present the work developed in collaboration with Chris Mears, Bart Demoen and Mark Wallace on symmetry detection and symmetry breaking. Regarding symmetry detection we present the first framework capable of accurately detecting symmetries of a problem (rather than of an instance of the problem). Regarding symmetry breaking, we present the first implementation that can safely be used as a default symmetry breaking method thanks to its low overhead and the fact it does not interfere with the search heuristic used.