In search of a better method to break row and column symmetries

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Complete row and column symmetry breaking in constraint satisfaction problems using the lex leader method is generally prohibitively costly. Double lex, which is derived from lex leader, is commonly used in practice as an incomplete symmetry-breaking method for row and column symmetries. This technique uses a row-wise ordering to construct the lex leader. For this reason, it is generally counterproductive to choose a search ordering that is not also row-wise. It seems logical that the search order should be used to pick the symmetry breaking technique, rather than the other way around. This paper surveys other possible orderings and investigates one particular ordering, snake ordering. From this we derive a corresponding incomplete set of symmetry breaking constraints, snake lex. We present experimental data comparing double lex and the snake lex, showing that snake lex is substantially faster than double lex in many cases.

Original languageEnglish
Title of host publicationSARA 2009 - Proceedings, 8th Symposium on Abstraction, Reformulation and Approximation
Pages97-104
Number of pages8
Publication statusPublished - 2009
Event8th Symposium on Abstraction, Reformulation and Approximation, SARA 2009 - Lake Arrowhead, CA, United States
Duration: 7 Jul 200910 Jul 2009

Publication series

NameSARA 2009 - Proceedings, 8th Symposium on Abstraction, Reformulation and Approximation

Conference

Conference8th Symposium on Abstraction, Reformulation and Approximation, SARA 2009
Country/TerritoryUnited States
CityLake Arrowhead, CA
Period7/07/0910/07/09

Fingerprint

Dive into the research topics of 'In search of a better method to break row and column symmetries'. Together they form a unique fingerprint.

Cite this