Skip to content

Research at St Andrews

GAPLex: Generalised Static Symmetry Breaking

Research output: Contribution to conferencePaper

Abstract

We describe a novel algorithm that statically breaks symmetry in CSPs by using computational group theory during search. This algorithm extends and generalises the commonly used double lex method for breaking symmetry in matrices. We showthat our new symmetry breaking method, GAPLex, is sound (will neither lose solutions nor return incorrect solutions) and complete (will return exactly one member from each class of symmetrically equivalent solutions). We demonstrate that our implementation of GAPLex is competitive with other methods, being effectively applicable to CSPs with large domains and less than full variable and/or value symmetry. We also describe how GAPLex can be combined with incomplete symmetry breaking methods such as double-lex to provide fast and complete symmetry breaking. We believe this to be the rst method that successfully combines the posting of symmetry breaking constraints before search, with symmetry breaking by analysis of search states.
Close

Details

Original languageEnglish
Pages17-23
Publication statusPublished - Sep 2006
EventSymCon'06: The Sixth International Workshop on Symmetry and Constraint Satisfaction Problems - Nantes, France
Duration: 25 Sep 2006 → …

Conference

ConferenceSymCon'06: The Sixth International Workshop on Symmetry and Constraint Satisfaction Problems
CountryFrance
CityNantes
Period25/09/06 → …

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Towards the calculation of Casimir forces for inhomogeneous planar media

    Xiong, C., Kelsey, T., Linton, S. A. & Leonhardt, U., 1 Oct 2014, Computer Mathematics: 9th Asian Symposium (ASCM2009), Fukuoka, December 2009, 10th Asian Symposium (ASCM2012), Beijing, October 2012, Contributed Papers and Invited Talks. Feng, R., Lee, W. & Sato, Y. (eds.). Springer, p. 171-180

    Research output: Chapter in Book/Report/Conference proceedingChapter

  2. Qualitative modelling via constraint programming

    Kelsey, T., Kotthoff, L., Jefferson, C. A., Linton, S. A., Miguel, I. J., Nightingale, P. & Gent, I. P., Apr 2014, In : Constraints. 19, 2, p. 163-173

    Research output: Contribution to journalArticle

  3. Casimir forces for inhomogeneous planar media

    Xiong, C., Kelsey, T., Linton, S. A. & Leonhardt, U., 25 Jan 2013, Journal of Physics: Conference Series. 1 ed. Vol. 401. 6 p. (Journal of Physics: Conference Series; vol. 410, no. 1).

    Research output: Chapter in Book/Report/Conference proceedingChapter

  4. Kisspeptin as a novel biomarker for pregnancy complications

    Phylactou, M., Abbara, A., Al-Memar, M., Chia Eng, P., Comninos, AN., Izzi-Engbeaya, C., Clarke, SA., Mills, E., Nadir, R., Sykes, M., Pacuszka, E., Yang, L., Fourie, H., Bech, P., Kelsey, T., Bourne, T. & Dhillo, WS., 5 Nov 2019, Endocrine Abstracts. BioScientifica Ltd., 1 p. OP5.4. (Endocrine Abstracts; vol. 65).

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

  5. Representation learning for minority and subtle activities in a smart home environment

    Rosales Sanabria, A., Kelsey, T., Dobson, S. A. & Ye, J., 28 Oct 2019, In : Journal of Ambient Intelligence and Smart Environments. Pre-press, p. 1-19

    Research output: Contribution to journalArticle

ID: 389640

Top