Research seminar:

	   Structure and Symmetry in Constraint Programming

By:
			   Meinolf Sellmann
		http://www.cs.brown.edu/people/sello/
		    Department of Computer Science
		      Brown University, RI, USA

On:
		    Thursday 24th of November 2005
		at 13:15 in room 1211 of www.MIC.uu.se

Abstract:

Constraint programming is one of the key techniques to solve
real-world problems.  Many such problems exhibit a lot of symmetry,
which complicates the solution process considerably.  Consequently,
symmetry breaking was found to be an important method to speed up the
search in constraint satisfaction problems (CSPs) that contain
symmetry.  When breaking symmetry by dominance detection, a
computationally efficient symmetry-breaking scheme can be achieved if
we can solve the dominance detection problem in polynomial time.  We
study the complexity of dominance detection when value and variable
symmetry appear simultaneously in CSPs.  We devise an efficient
dominance detection algorithm for CSPs that yields symmetry-free
search trees and that is based on the abstraction to the actual,
intuitive structure of a symmetric CSP.