Breaking row and column symmetries in matrix models

P. Flener; A.M. Frisch; B. Hnich; Z. Kiziltan; I. Miguel; J. Pearson; T. Walsh

doi:10.1007/3-540-46135-3_31

Breaking row and column symmetries in matrix models

P. Flener, A.M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, J. Pearson, T. Walsh

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English
Title of host publication	Proceedings of the 8th International Conference on Principles and Practice of Constraint Programmin
Place of Publication	Berlin / Heidelberg
Publisher	Springer
Pages	462-477
Number of pages	15
ISBN (Print)	978-3-540-44120-5
DOIs	https://doi.org/10.1007/3-540-46135-3_31
Publication status	Published - Sept 2002
Event	Principles and Practice of Constraint Programming - (CP 2002) - Ithaca, New York, United States Duration: 23 Jul 2001 → 26 Jul 2001

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2470

Conference

Conference	Principles and Practice of Constraint Programming - (CP 2002)
Country/Territory	United States
City	Ithaca, New York
Period	23/07/01 → 26/07/01

Access to Document

10.1007/3-540-46135-3_31

http://dx.doi.org/10.1007/3-540-46135-3_31

Cite this

@inproceedings{13e64bce06344280bdefe81703ca8637,

title = "Breaking row and column symmetries in matrix models",

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.",

author = "P. Flener and A.M. Frisch and B. Hnich and Z. Kiziltan and I. Miguel and J. Pearson and T. Walsh",

year = "2002",

month = sep,

doi = "10.1007/3-540-46135-3_31",

language = "English",

isbn = "978-3-540-44120-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "462--477",

booktitle = "Proceedings of the 8th International Conference on Principles and Practice of Constraint Programmin",

address = "Germany",

note = "Principles and Practice of Constraint Programming - (CP 2002) ; Conference date: 23-07-2001 Through 26-07-2001",

}

Flener, P, Frisch, AM, Hnich, B, Kiziltan, Z, Miguel, I, Pearson, J & Walsh, T 2002, Breaking row and column symmetries in matrix models. in Proceedings of the 8th International Conference on Principles and Practice of Constraint Programmin. Lecture Notes in Computer Science, vol. 2470, Springer, Berlin / Heidelberg, pp. 462-477, Principles and Practice of Constraint Programming - (CP 2002), Ithaca, New York, United States, 23/07/01. https://doi.org/10.1007/3-540-46135-3_31

Breaking row and column symmetries in matrix models. / Flener, P.; Frisch, A.M.; Hnich, B. et al.
Proceedings of the 8th International Conference on Principles and Practice of Constraint Programmin. Berlin / Heidelberg: Springer, 2002. p. 462-477 (Lecture Notes in Computer Science; Vol. 2470).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Breaking row and column symmetries in matrix models

AU - Flener, P.

AU - Frisch, A.M.

AU - Hnich, B.

AU - Kiziltan, Z.

AU - Miguel, I.

AU - Pearson, J.

AU - Walsh, T.

PY - 2002/9

Y1 - 2002/9

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.

U2 - 10.1007/3-540-46135-3_31

DO - 10.1007/3-540-46135-3_31

M3 - Conference contribution

SN - 978-3-540-44120-5

T3 - Lecture Notes in Computer Science

SP - 462

EP - 477

BT - Proceedings of the 8th International Conference on Principles and Practice of Constraint Programmin

PB - Springer

CY - Berlin / Heidelberg

T2 - Principles and Practice of Constraint Programming - (CP 2002)

Y2 - 23 July 2001 through 26 July 2001

ER -