Symmetry in Models and Search
Symmetry Detection & Symmetry Breaking
- Breaking: We introduced the notion of structural symmetry breaking (SSB), which aims at exploiting the combinatorial structure of various classes of practically relevant problems in order to make symmetry breaking tractable. We distinguish dynamic SSB (where a special-purpose search procedure is used) [VFPÅ03] from static SSB (where so-called symmetry-breaking constraints are added to the model) [FPSV06], and compare their strengths. We chart the frontier of tractability for SSB. We address rotation variable symmetry, possibly in the presence of value symmetry [FP08].
- Detection: Our tractable approach [VFPÅ05] could be called structural symmetry detection, for the same reason.
Conditional Symmetry Breaking
Cooperation with the group of Ian Gent and Steve Linton at the University of St Andrews, UK.
Selected Publications: [GKL+07]