Skip to content

Research at St Andrews

Conditional symmetry breaking

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

DOI

Abstract

We introduce the study of Conditional symmetry breaking in constraint programming. This arises in a sub-problem of a constraint satisfaction problem, where the sub-problem satisfies some condition under which additional symetries hold. Conditional symmetry can cause redundancy in a systematic search for solutions. Breaking this symmetry is an important part of solving a constraint satisfaction problem effectively. We demonstrate experimentally that three methods, well-known for breaking unconditional symmetries, can be applied to conditional symmetries. These are: adding conditional symmetry-breaking constraints, reformulating the problem to remove the symmetry, and augmenting the search process to break the conditional symmetry dynamically through the use of a variant of Symmetry Breaking by Dominance Detection (SBDD).

Close

Details

Original languageEnglish
Title of host publicationPrinciples and practice of constraint programming--CP 2005: 11th international conference, CP 2005, Sitges, Spain, October 1-5, 2005 : Proceedings
EditorsPeter Van Beek
PublisherSpringer
Pages256-270
Number of pages15
ISBN (Print)978-3-540-29238-8
DOIs
Publication statusPublished - Oct 2005

Publication series

NameLecture notes in computer science
Volume3709
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

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

View graph of relations

Related by author

  1. 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

  2. Generating custom propagators for arbitrary constraints

    Gent, I. P., Jefferson, C., Linton, S., Miguel, I. & Nightingale, P., Jun 2014, In : Artificial Intelligence. 211, p. 1-33 33 p.

    Research output: Contribution to journalArticle

  3. Groupoids and Conditional Symmetry

    Gent, I. P., Kelsey, T. W., Linton, S. A., Pearson, J., Roney-Dougal, C. M. & Bessiere, C., Sep 2007, p. 823-830.

    Research output: Contribution to conferencePaper

  4. Search in the Patience Game `Black Hole'

    Gent, I. P., Kelsey, T. W., Jefferson, C., Lynce, I., Miguel, I. J., Nightingale, P., Smith, BM. & Armagan Tarim, S., 2007, In : AI Communications. 20, 3, p. 211-226 16 p.

    Research output: Contribution to journalArticle

  5. Symmetry and consistency

    Gent, I. P., Kelsey, T., Linton, S. & Roney-Dougal, C., 2005, Principles and Practice of Constraint Programming - CP 2005: Proceedings of the 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005. van Beek, P. (ed.). Springer-Verlag, p. 271-285 15 p. (Lecture Notes in Computer Science; vol. 3709).

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

ID: 2368257

Top