Skip to content

Research at St Andrews

Breaking conditional symmetry in automated constraint modelling with CONJURE

Research output: ResearchChapter

DOI

Open Access permissions

Open

Abstract

Many constraint problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: model symmetries. We present a systematic method by which the automated constraint modelling tool CONJURE can break conditional symmetry as it enters a model during refinement. Our method extends, and is compatible with, our previous work on automated symmetry breaking in CONJURE. The result is the automatic and complete removal of model symmetries for the entire problem class represented by the input specification. This applies to arbitrarily nested conditional symmetries and represents a significant step forward for automated constraint modelling.
Close

Details

Original languageEnglish
Title of host publicationECAI 2014
EditorsT. Schaub, G. Friedrich, B. O'Sullivan
PublisherIOS Press
Pages3-8
Number of pages6
Volume263
ISBN (Print)9781614994183
DOIs
StatePublished - 2014

Publication series

NameFrontiers in Artificial Intelligence and Applications
PublisherIOS Press
Volume263
ISSN (Print)0922-6389

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

View graph of relations

Related by author

  1. Automatically improving constraint models in Savile Row

    Nightingale, P., Akgün, Ö., Gent, I. P., Jefferson, C., Miguel, I. & Spracklen, P. Oct 2017 In : Artificial Intelligence. 251, p. 35-61 27 p.

    Research output: Research - peer-reviewArticle

  2. Exploiting short supports for improved encoding of arbitrary constraints into SAT

    Akgün, Ö., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W. 2016 Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Rueher, M. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 9892)

    Research output: ResearchConference contribution

  3. Automatically Improving Constraint Models in Savile Row through Associative-Commutative Common Subexpression Elimination

    Nightingale, P., Akgun, O., Gent, I. P., Jefferson, C. & Miguel, I. Sep 2014 Principles and Practice of Constraint Programming. OSullivan, B. (ed.). Cham: Springer, p. 590-605 16 p. (Lecture Notes in Computer Science; vol. 8656)

    Research output: ResearchConference contribution

  4. An Automated Constraint Modelling and Solving Toolchain

    Akgun, O., Frisch, A. M., Gent, I. P., Hussain, B. S., Jefferson, C. A., Kotthoff, L., Miguel, I. J. & Nightingale, P. W. 2013 ARW 2013 - 20th Automated Reasoning Workshop.

    Research output: ResearchConference contribution

  5. Automated Symmetry Breaking and Model Selection in Conjure

    Akgun, O., Frisch, A. M., Gent, I. P., Hussain, B. S., Jefferson, C. A., Kotthoff, L., Miguel, I. J. & Nightingale, P. W. 2013 CP 2013 - Principles and Practice of Constraint Programming, 19th International Conference.

    Research output: ResearchConference contribution

ID: 172487935