Symmetry

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.

Cooperation with the group of Ian Gent and Steve Linton at the University of St Andrews, UK.

Selected Publications: [GKL+07]