Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Snake Lex: An Alternative to Double Lex

Andrew Grayland17 Contact Information, Ian Miguel17 Contact Information and Colva M. Roney-Dougal18 Contact Information

(17)  School of Comp. Sci., St Andrews, UK
(18)  School of Maths and Stats, St Andrews, UK
Abstract
Complete row and column symmetry breaking in constraint models 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. Double lex is based on a row-wise canonical variable ordering. However, this choice is arbitrary. We investigate other canonical orderings and focus on one in particular: snake ordering. From this we derive a corresponding incomplete set of symmetry breaking constraints, snake lex. Experimental data comparing double lex and snake lex shows that snake lex is substantially better than double lex in many cases.

Contact Information Andrew Grayland
Email: andyg@cs.st-and.ac.uk

Contact Information Ian Miguel
Email: ianm@cs.st-and.ac.uk

Contact Information Colva M. Roney-Dougal
Email: colva@mcs.st-and.ac.uk
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.111 • Server: MPWEB26
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)