Call for Papers & Call for Participation

The Second International Workshop
on Symmetry in Constraint Satisfaction Problems

CP'02 Workshop
Sunday 8 September 2002
Ithaca, NY, USA

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.

Programme Committee Chairs

Programme Committee Members

Submission Process (over!)

Extended abstracts of 4 to 8 LNCS/article-style pages are to be emailed, as PS or PDF files, to by Wednesday 10 July 2002.

Additionally, statements of interest of 1 page may be emailed, as PS or PDF files, to 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.

Important Dates

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

Accepted Papers, Schedule, Proceedings, and Slides

Cover page and table of contents of the proceedings

Papers (presented at the workshop)

9:00 - 9:40
Symmetry Breaking Constraints for Matrix Models (Paper)
Zeynep Kiziltan and Barbara M. Smith
Constraint Programming with Multisets (Paper) (Joined Slides)
Zeynep Kiziltan and Toby Walsh

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

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

Statements of Interest (not presented at the workshop) (full papers and presentations at the CP'02 main conference)

Solving Kirkman's Schoolgirl Problem in a Few Seconds (Slides) (Paper)
Nicolas Barnier and Pascal Brisset

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

Pierre Flener and Justin Pearson
Last modified: 18 September 2002