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
Country/TerritoryFrance
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 journalArticlepeer-review

  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. Diagnostic and predictive accuracy of anti-Mullerian hormone for ovarian function after chemotherapy in premenopausal women with early breast cancer

    Anderson, R. A., Kelsey, T., Perdix, A., Olympios, N., Duhamel, O., Lambertini, M. & Clatot, F., 8 Jan 2022, (E-pub ahead of print) In: Breast Cancer Research and Treatment. First Online, 10 p.

    Research output: Contribution to journalArticlepeer-review

  5. Ovarian function and fertility preservation for young people treated for cancer

    Caprioli, S., Kelsey, T. & Wallace, W. H. B., 1 Jan 2022, Female and male fertility preservation. Grynberg, M. & Patrizio, P. (eds.). Cham: Springer, p. 35-45

    Research output: Chapter in Book/Report/Conference proceedingChapter

ID: 389640

Top