An important class of symmetries in constraint programming arises in matrices of decision variables (we assume 2 dimensional matrices without loss of generality) where rows and columns represent indistinguishable objects and are therefore symmetries. We can permute any two rows as well as two columns of a matrix with row and column symmetry without affecting any (partial) assignments. An n * m matrix with row and column symmetry has n!m! symmetries, which increase super-exponentially thus it can be very expensive to visit all the symmetric branches of the search tree. In order to break such symmetries effectively, we investigate ordering constraints that can be posted on matrices without removing feasible solutions.
展开▼
