| Pattern name |
MatrixSymmetry. |
| Context | A matrix model containing an array of decision variables with (partial) row and/or column symmetry. |
| Problem |
Symmetry increases the size of the search space. |
| Forces |
Eliminating all symmetry can be too expensive. Eliminating no symmetry can leave too much search. |
| Solution |
Consider posting lex ordering constraints on symmetric rows and columns. Alternatively post lex ordering in one dimension and multiset ordering in the other. If supported, consider posting additional all-perms ordering constraints. |
| Example |
Balanced Incomplete Block Design generation,
prob028 in
CSPLib. |
| References |
Breaking Row and Column Symmetries in Matrix Models
(pdf,
legal ps,
letter ps)
Pierre Flener, Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Justin Pearson and Toby Walsh. Proceedings of CP-2002, 2002. Global Constraints for Lexicographic Orderings (pdf, legal ps, letter ps) Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel and Toby Walsh. Proceedings of CP-2002, 2002. Multiset Ordering Constraints (pdf, legal ps, letter ps) Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, and Toby Walsh. Proceedings of IJCAI-2003, 2003. Constraints for Breaking More Row and Column Symmetries (pdf) Alan. Frisch, Chris Jefferson and Ian Miguel. Proceedings of CP-2003, 2003.
|