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

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.