Symmetry in Constraint Satisfaction Problems (SymCon'10)

the 16th International Conference on the

Principles and Practice of Constraint Programming (CP'10)

Monday 6 September 2010

This is the 10th workshop of the very successful SymCon series, founded by this year's programme chairs in 2001. It will be a half-day workshop open to anyone interested in the topic. The event will have a strong workshop flavour, with ample time allocated to discussion.

List of accepted papers (cover sheet and preface of the proceedings):

14:00 - 14:10 | Opening |

14:10 - 14:40 | A Partial Taxonomy of Substitutability and Interchangeability (PDF) |

14:40 - 15:10 | Internal Symmetry (PDF) |

15:10 - 15:40 | Symmetries and Lazy Clause Generation (PDF) |

15:40 - 16:00 | Refreshments |

16:00 - 17:00 | Invited talk: Boosting Symmetry Breaking through Propagation |

17:00 - 17:30 | Arities of Symmetry Breaking Constraints (PDF) |

17:30 - 18:00 | Symmetries of Symmetry Breaking Constraints (ECAI'10 paper) |

18:00 - 18:00 | Closing |

Pierre Flener (co-chair) | Uppsala University, Sweden |

Ian P. Gent | University of St Andrews, Scotland, UK |

Justin Pearson (co-chair) | Uppsala University, Sweden |

Karen Petrie | University of Dundee, Scotland, UK |

Jean-François Puget | IBM, France |

Lakhdar Sais | Université d'Artois, France |

Mark Wallace | Monash University, Australia |

Toby Walsh | University of New South Wales, Australia |

A symmetry is a transformation that preserves solutions that are considered equivalent. For instance, rotating a chess board 180 degrees gives a board that is indistinguishable from the original board. Symmetry increases the apparent complexity of combinatorial problems. In the presence of symmetry, a constraint solver may waste a large amount of time considering symmetric but equivalent assignments or partial assignments. Hence, dealing with symmetry is often crucial to the success of solving such combinatorial problems efficiently.

Workshop topics include (but are not limited to):

- Symmetry definition: semantic symmetry, syntactic symmetry, constraint symmetry, solution symmetry
- Automatic symmetry detection: static and dynamic approaches
- Global symmetry detection and elimination
- Local (conditional) symmetry detection and elimination
- Combining symmetry-breaking techniques
- Exploiting weak forms of symmetries like "dominance" and "almost-symmetries"
- Case studies of problems that exhibit interesting symmetries
- Application of computational group theory techniques to symmetry breaking
- Heuristics that use information about symmetry to guide search
- Elimination and avoidance of symmetry by reformulation
- Dynamic avoidance of symmetric states during search
- Complexity analysis of symmetry-breaking techniques
- Comparison of symmetry-breaking techniques in constraint programming with techniques for dealing with symmetry in other search domains
- Symmetry in (quantified) Boolean formulae
- Symmetry in finite model search in first-order logic
- Novel exploitation of symmetry in varied search domains of interest to the CP community

Submissions must be formatted in the Lecture Notes in Computer Science (LNCS) style and must not exceed 15 pages. Submissions of shorter papers, including position papers, are welcome. Papers must be submitted in PDF format using EasyChair.

All submissions will be reviewed and those that are well written and make a worthwhile contribution to the topic of the workshop will be accepted for publication in the workshop proceedings. The proceedings will be available electronically at CP'10. At least one author of each accepted paper must attend the workshop.

Submission deadline | Wednesday 30 June 2010 (closed) |

Notification of acceptance | Monday 9 August 2010 (done) |

Camera-ready copy deadline | Thursday 19 August 2010 (closed) |

Workshop | Monday 6 September 2010 |

Last modified: Tue Aug 31 07:55:47 CEST 2010