Abstract:

Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such ‘matrix models’ often have symmetry. In particular, they often have row and column symmetry as the rows and columns can freely be permuted without affecting the satisfiability of assignments. Row and column symmetries can be very problematic in a systematic search as they grow super-exponentially and create a significant amount of redundancy in the search space. This talk is an overview of my PhD dissertation and it describes some of the first work for dealing with row and column symmetries efficiently and effectively. Row and column symmetry has been recognised by many other researchers as being critical in a wide range of application domains. It is now one of the most active areas of research in symmetry in CSPs. The ordering constraints and the propagators proposed in this dissertation are central to some of the mechanisms proposed for dealing with row and column symmetries.

Zeynep Kiziltan is an assistant professor at the department of Computer Science of the University of Bologna in Italy. She received her PhD degree in 2004 from the University of Uppsala in Sweden where she is later appointed as associate professor. The PhD thesis of Dr. Kiziltan has won the 2004 best thesis award of the European Coordinating Committee for Artificial Intelligence.

Date: 2007-Sep-07     Time: 11:00:00     Room: 336

For more information:

• ines@sat.inesc-id.pt