Breaking row and column symmetries in matrix models

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

121 Citations (Scopus)

Abstract

We identify an important class of symmetries in constraint programming, arising from matrices of decision variables where rows and columns can be swapped. Whilst lexicographically ordering the rows(columns) breaks all the row (column) symmetries, lexicographically ordering both the rows and the columns fails to break all the compositions of the row and column symmetries. Nevertheless, our experimental results show that this is effective at dealing with these compositions of symmetries. We extend these results to cope with symmetries in any number of dimensions, with partial symmetries, and with symmetric values. Finally, we identify special cases where all compositions of the row and column symmetries can be eliminated by the addition of only a linear number of symmetry-breaking constraints.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings
EditorsPascal Van Hentenryck
PublisherSpringer-Verlag
Pages462-477
Number of pages16
ISBN (Print)3540441204, 9783540441205
DOIs
Publication statusPublished - 2002
Event8th International Conference on Principles and Practice of Constraint Programming, CP 2002 - Ithaca, United States
Duration: 9 Sept 200213 Sept 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2470
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Principles and Practice of Constraint Programming, CP 2002
Country/TerritoryUnited States
CityIthaca
Period9/09/0213/09/02

Fingerprint

Dive into the research topics of 'Breaking row and column symmetries in matrix models'. Together they form a unique fingerprint.

Cite this