Symmetry in Models and Search
See SymCon: The International Workshops on Symmetry in Constraint Satisfaction Problems.
Symmetry Detection & Symmetry Breaking
CORSA project with Pascal Van Hentenryck
and Meinolf Sellmann at Brown University, Providence, Rhode Island, USA:
- 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.
Also see Pierre Flener's invited talk
at SymCon'09.
Conditional Symmetry Breaking
Cooperation with the group of Ian Gent and Steve Linton at the University of St Andrews, UK.
Selected Publications: [GKL+07]