TY - GEN
T1 - Breaking row and column symmetries in matrix models
AU - Flener, Pierre
AU - Frisch, Alan M.
AU - Hnich, Brahim
AU - Kiziltan, Zeynep
AU - Miguel, Ian
AU - Pearson, Justin
AU - Walsh, Toby
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84956998918&partnerID=8YFLogxK
U2 - 10.1007/3-540-46135-3_31
DO - 10.1007/3-540-46135-3_31
M3 - Conference contribution
AN - SCOPUS:84956998918
SN - 3540441204
SN - 9783540441205
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 462
EP - 477
BT - Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings
A2 - Van Hentenryck, Pascal
PB - Springer-Verlag
T2 - 8th International Conference on Principles and Practice of Constraint Programming, CP 2002
Y2 - 9 September 2002 through 13 September 2002
ER -