Call for Papers & Participation
CP'01 Post-Conference Workshop
1 December 2001, Paphos, Cyprus

SymCon'01 -- Symmetry in Constraint Satisfaction Problems

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.

Programme Committee Chairs

• Pierre Flener
• Justin Pearson

Programme Committee Members

• Rolf Backofen
• Ian Gent
• Pedro Meseguer
• Michela Milano
• Barbara M. Smith
• Toby Walsh

Submission Process (over!)

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.

Important Dates

Accepted Papers

Papers to be presented at the workshop

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

Papers not to be presented at the workshop (for time reasons)

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