Uppsala University Department of Information Technology

Technical Report 2001-022

Symmetry in Matrix Models

Pierre Flener, Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Justin Pearson, and Toby Walsh

September 2001

Abstract:
Many constraint satisfaction problems (such as scheduling, assignment, and configuration) can be modelled as constraint programs based on matrices of decision variables. In such matrix models, symmetry is an important feature. We study and generalise symmetry-breaking techniques, such as lexicographic ordering, and propose a labelling technique achieving the same effect.

Note: Also released as Technical Report APES-30-2001 of the APES group, 2001, available at http://www.dcs.st-and.ac.uk/~apes/reports/apes-30-2001.ps.gz. Appears in the Proceedings of the CP-01 Workshop on Symmetry in Constraints. 7th International Conference on the Principles and Practice of Constraint Programming, 2001

Available as compressed Postscript (44 kB, no cover)

Download BibTeX entry.



Uppsala Universitet