There are many constraint satisfaction problems that have a great deal of symmetry. This symmetry can be used to increase the efficiency of search by avoiding exploring paths that have already been shown to be a dead-end in a symmetrical part of the search tree, or by only enumerating one solution per equivalence class. This process is often referred to as symmetry breaking or symmetry exclusion. For example, when colouring a graph, many of the solutions are related simply by rotating the colours. Or, for example, when solving a tournament timetabling problem, at the start it does not matter in which order the participants play the first games. This workshop is to focus on the analysis and development of techniques to detect and exploit symmetry in constraint satisfaction problems.
This will be a half-day workshop, with open attendance. People wishing to give a talk should submit a 4-to-8-page extended abstract, in article or LNCS style. If necessary for time reasons, only a subset of the submitted works will be able to be presented: a selection will then be made by the Programme Committee. Also, informal proceedings will be assembled from selected abstracts and all statements of interest. Work-in-progress may thus be submitted, and material from other submissions may thus be reused.
This workshop will be relevant to people who are interested either in increasing the efficiency of search or in understanding the structure of constraint satisfaction problems. So far, different techniques for symmetry breaking have been studied: those acting on the model, as well as techniques that alter the search procedure (by altering the branching strategy or dynamically removing symmetries). This purpose of this workshop is to bring together people interested in this fast growing area.
Extended abstracts of 4 to 8 LNCS/article-style pages are to be emailed, as PS or PDF files, to the programme chairs by Thursday 20 September 2001.
Additionally, statements of interest of 1 page may be emailed, as PS or PDF files, to the programme chairs by Sunday 14 October 2001.
All workshop attendees must pay the CP/ICLP'01 workshop registration fee.
| Extended-abstract deadline: | Thursday 20 September 2001 |
| Notification deadline: | Friday 12 October 2001 |
| Camera-ready-copy deadline: | Sunday 21 October 2001 |
| Statement-of-interest deadline: | Sunday 21 October 2001 |
| Workshop: | Saturday 1 December 2001 |
Warwick Harvey
Symmetry Breaking and the Social Golfer Problem
Ian Miguel
Symmetry-Breaking in Planning: Schematic Constraints
Ian P. Gent
A Symmetry Breaking Constraint for Indistinguishable Values
Raik Brinkmann
Using Symmetry for Problem Reduction in Bounded-Model-Checking on
the Register-Transfer-Level
Pierre Flener, Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel,
Justin Pearson, and Toby Walsh
Symmetry in Matrix Models
Barbara M. Smith and Ian P. Gent
Reducing Symmetry in Matrix Models: SBDS vs. Constraints
Ana Paula Tomas and Evelyne Contejean
On Symmetries in Systems Coming from AC-Unification of Higher-Order Patterns
Iain D. Stalker and Patricia M. Hill
The Symmetry Domain
Iain McDonald
Unique Symmetry Breaking in CSPs Using Group Theory
Nicoleta Neagu and Boi Faltings
Symmetry in CSP Solutions