There are many constraint satisfaction problems that have a great deal of symmetry. For example, when colouring a graph, many of the solutions are related by rotating the colours. Similarly, when solving a tournament timetabling problem, it does not matter in which order the participants play the first games: many of the solutions are related by permuting the participants. Symmetry in constraint satisfaction problems can be exploited to increase the efficiency of search. This can be done by avoiding exploring paths that have already been shown to be a dead-end in a symmetrical part of the search tree, or by adding constraints so that (ideally) only one assignment per equivalence class is enumerated. This process is often referred to as symmetry breaking or symmetry reduction.
This workshop is to focus on the analysis and development of techniques to detect and exploit symmetry in constraint satisfaction problems. It is the second workshop in a series that started with SymCon'01 at CP'01 in Paphos, Cyprus.
This will be a half-day workshop, with open attendance. Researchers wishing to give talks should submit 4-to-8-page extended abstracts, 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. Towards making the informal on-line proceedings a who-is-who on symmetry, 1-page statements of interest are also solicited (say for accepted papers on symmetry at the CP'02 main conference, or for submitted workshop papers that cannot be presented for time reasons). Work-in-progress may be submitted, and material from other submissions may be reused.
Extended abstracts of 4 to 8 LNCS/article-style pages are to be emailed, as PS or PDF files, to PierreF@csd.uu.se by Wednesday 10 July 2002.
Additionally, statements of interest of 1 page may be emailed, as PS or PDF files, to PierreF@csd.uu.se by Monday 5 August 2002.
At least one author of each presented submission must attend the workshop. All workshop attendees must pay the CP'02 workshop registration fee.
| Extended-abstract deadline: | Wednesday 10 July 2002 |
| Notification deadline: | Friday 26 July 2002 |
| Camera-ready-copy deadline: | Monday 5 August 2002 |
| Statement-of-interest deadline: | Monday 5 August 2002 |
| Workshop: | Sunday 8 September 2002 |
9:40 - 10:10
Supersymmetric Modelling for Local Search
(Paper)
(Slides)
Steven Prestwich
10:10 - 10:30
Symmetry Breaking via Dominance Detection for Lookahead Constraint Solvers
(Paper)
(Slides)
Igor Razgon and Amnon Meisels
10:30 - 11:00
Refreshments
11:00 - 11:30
Symmetry Breaking for Boolean Satisfiability:
The Mysteries of Logic Minimization
(Paper)
(Slides)
Fadi A. Aloul, Igor L. Markov, and Karem A. Sakallah
11:30 - 12:00
Breaking All the Symmetries in Matrix Models:
Results, Conjectures, and Directions
(Paper)
(Slides)
Pierre Flener and Justin Pearson
12:00 - 12:30
Group-Graphs Associated with Row and Column Symmetries of Matrix Models:
Some Observations
(Paper)
(Slides)
Zeynep Kiziltan and Michela Milano
12:30 - 13:30
Lunch
Breaking Row and Column Symmetries in Matrix Models
(Abstract)
(Slides)
(Paper)
Pierre Flener, Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan,
Ian Miguel, Justin Pearson, and Toby Walsh
Groups and Constraints: Symmetry Breaking During Search
(Abstract)
(Slides)
(Paper)
Ian P. Gent, Warwick Harvey, and Tom Kelsey
Partial Symmetry Breaking
(Abstract)
(Slides)
(Paper)
Iain McDonald and Barbara Smith
Symmetry Breaking Revisited
(Abstract)
(Slides)
(Paper)
Jean-Francois Puget
