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 - Funding: This work is partially supported by grant 221-99-369 of VR (the Swedish Research Council), by institutional grant IG2001-67 of STINT (the Swedish Foundation for In- ternational Cooperation in Research and Higher Education), and grant GR/N16129 of EPSRC(the UK Engineering and Physical Sciences Research Council).
PY - 2002/1/1
Y1 - 2002/1/1
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 - https://doi.org/10.1007/3-540-46135-3
U2 - 10.1007/3-540-46135-3_31
DO - 10.1007/3-540-46135-3_31
M3 - Conference contribution
AN - SCOPUS:84956998918
SN - 9783540441205
T3 - Lecture notes in computer science
SP - 462
EP - 477
BT - Principles and practice of constraint programming
A2 - Hentenryck, Pascal
PB - Springer-Verlag
CY - Heidelberg
T2 - 8th International Conference on Principles and Practice of Constraint Programming, CP 2002
Y2 - 9 September 2002 through 13 September 2002
ER -