Monday March 11, 2013 at 16h30 in Celestijnenlaan 200A (auditorium 00.225)
Symmetry in Search Problems
by Bart Bogaerts (PhD student DTAI)
Many search problems are highly symmetrical. Knowledge about these symmetries might help humans to quickly see whether there are solutions (e.g. the pigeonhole problem) or to guide the decisions a human makes when solving this problem (e.g. graph coloring). In this seminar, we discuss how the existence of symmetries can be exploited in search algorithms. More specifically, we will present two symmetry breaking methods for SAT solvers: Shatter (static symmetry breaking) and SP(SAT) (dynamic symmetry breaking). Even though this talk will mainly be limited to symmetry breaking for SAT solvers, all presented ideas can easily be transfered to other domains, such as for example Constraint Programming.