CL Seminar Series 2004

Speaker: Toby Walsh, University College
Cork

Date: Jan.15, 2004

Place and Time: ASB9705 1:30pm

Title: Symmetry in Constraint Programming

Abstract:

The world is full of symmetry. When solving combinatorial problems using search
techniques like constraint programming, symmetry may be inherent in the problem
or may arise through modelling it as a constraint problem (e.g. naming essentially
indistinguishable objects). In either case, symmetry can lead to redundant search,
as many symmetrically equivalent blind alleys may be explored wastefully. To
avoid this, symmetry-breaking constraints can be added, to exclude all but one
of each equivalence class of solutions. Alternatively search methods can be
adapted to prevent them searching symmetric states to those already visited.
I will describe recent results in dealing with symmetry in constraint programming
and outline some of the open problems in the field.

http://www.cs.sfu.ca/~cl