Constraints for breaking more row and column symmetries

A M Frisch; C Jefferson; I Miguel

Constraints for breaking more row and column symmetries

A M Frisch, C Jefferson, I Miguel

Computer Science

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

Abstract

Constraint programs containing a matrix of two (or more) dimensions of decision variables often have row and column symmetries: in any assignment to the variables the rows can be swapped and the columns can be swapped without affecting whether or not the assignment is a solution. This introduces an enormous amount of redundancy when searching a space of partial assignments. It has been shown previously that one can remove consistently some of these symmetries by extending such a program with constraints that require the rows and columns to be lexicographically ordered. This paper identifies and studies the properties of a new additional constraint-the first row is less than or equal to all permutations of all other rows-that can be added consistently to break even more symmetries. Two alternative implementations of this stronger symmetry-breaking method are investigated, one of which employs a new algorithm that in time linear in the size of the matrix enforces the constraint that the first row is less than or equal to all permutations of all other rows. It is demonstrated experimentally that our method for breaking more symmetries substantially reduces search effort.

Original language	English
Title of host publication	PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2003, PROCEEDINGS
Editors	F Rossi
Place of Publication	BERLIN
Publisher	Springer
Pages	318-332
Number of pages	15
ISBN (Print)	3-540-20202-1
Publication status	Published - 2003
Event	9th International Conference on Principles and Practice of Constraint Programming - Cork Duration: 29 Sept 2003 → 3 Oct 2003

Conference

Conference	9th International Conference on Principles and Practice of Constraint Programming
City	Cork
Period	29/09/03 → 3/10/03

Cite this

@inproceedings{3202f0f87dd740f0a2f7cd12a391b56a,

title = "Constraints for breaking more row and column symmetries",

abstract = "Constraint programs containing a matrix of two (or more) dimensions of decision variables often have row and column symmetries: in any assignment to the variables the rows can be swapped and the columns can be swapped without affecting whether or not the assignment is a solution. This introduces an enormous amount of redundancy when searching a space of partial assignments. It has been shown previously that one can remove consistently some of these symmetries by extending such a program with constraints that require the rows and columns to be lexicographically ordered. This paper identifies and studies the properties of a new additional constraint-the first row is less than or equal to all permutations of all other rows-that can be added consistently to break even more symmetries. Two alternative implementations of this stronger symmetry-breaking method are investigated, one of which employs a new algorithm that in time linear in the size of the matrix enforces the constraint that the first row is less than or equal to all permutations of all other rows. It is demonstrated experimentally that our method for breaking more symmetries substantially reduces search effort.",

author = "Frisch, {A M} and C Jefferson and I Miguel",

year = "2003",

language = "English",

isbn = "3-540-20202-1",

pages = "318--332",

editor = "F Rossi",

booktitle = "PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2003, PROCEEDINGS",

publisher = "Springer",

address = "Germany",

note = "9th International Conference on Principles and Practice of Constraint Programming ; Conference date: 29-09-2003 Through 03-10-2003",

}

TY - GEN

T1 - Constraints for breaking more row and column symmetries

AU - Frisch, A M

AU - Jefferson, C

AU - Miguel, I

PY - 2003

Y1 - 2003

N2 - Constraint programs containing a matrix of two (or more) dimensions of decision variables often have row and column symmetries: in any assignment to the variables the rows can be swapped and the columns can be swapped without affecting whether or not the assignment is a solution. This introduces an enormous amount of redundancy when searching a space of partial assignments. It has been shown previously that one can remove consistently some of these symmetries by extending such a program with constraints that require the rows and columns to be lexicographically ordered. This paper identifies and studies the properties of a new additional constraint-the first row is less than or equal to all permutations of all other rows-that can be added consistently to break even more symmetries. Two alternative implementations of this stronger symmetry-breaking method are investigated, one of which employs a new algorithm that in time linear in the size of the matrix enforces the constraint that the first row is less than or equal to all permutations of all other rows. It is demonstrated experimentally that our method for breaking more symmetries substantially reduces search effort.

AB - Constraint programs containing a matrix of two (or more) dimensions of decision variables often have row and column symmetries: in any assignment to the variables the rows can be swapped and the columns can be swapped without affecting whether or not the assignment is a solution. This introduces an enormous amount of redundancy when searching a space of partial assignments. It has been shown previously that one can remove consistently some of these symmetries by extending such a program with constraints that require the rows and columns to be lexicographically ordered. This paper identifies and studies the properties of a new additional constraint-the first row is less than or equal to all permutations of all other rows-that can be added consistently to break even more symmetries. Two alternative implementations of this stronger symmetry-breaking method are investigated, one of which employs a new algorithm that in time linear in the size of the matrix enforces the constraint that the first row is less than or equal to all permutations of all other rows. It is demonstrated experimentally that our method for breaking more symmetries substantially reduces search effort.

M3 - Conference contribution

SN - 3-540-20202-1

SP - 318

EP - 332

BT - PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2003, PROCEEDINGS

A2 - Rossi, F

PB - Springer

CY - BERLIN

T2 - 9th International Conference on Principles and Practice of Constraint Programming

Y2 - 29 September 2003 through 3 October 2003

ER -