Automatic generation of constraints for partial symmetry breaking

Christopher Jefferson, Karen E. Petrie

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

    8 Citations (Scopus)


    Constraint Satisfaction Problems (CSPs) are often highly symmetric. Symmetries can give rise to redundant search, since subtrees may be explored which are symmetric to subtrees already explored. To avoid this redundant search, constraint programmers have designed methods, which try to exclude all but one in each equivalence class of solutions. One problem with many of the symmetry breaking methods that eliminate all the symmetry is that they can have a large running overhead. To counter this flaw many CP practitioners have looked for methods that only eliminate a subset of the symmetries, so called partial symmetry breaking methods, but do so in an efficient manner. Partial symmetry breaking methods often work only when the problem is of a certain type. In this paper, we introduce a new method of finding a small set of constraints which provide very efficient partial symmetry breaking. This method works with all problem classes and modelling techniques.
    Original languageEnglish
    Title of host publicationPrinciples and practice of constraint programming - CP 2011
    Subtitle of host publication7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings
    EditorsJimmy Lee
    Place of PublicationBerlin
    Number of pages15
    ISBN (Electronic)9783642237867
    ISBN (Print)9783642237850
    Publication statusPublished - 2011
    Event17th International Conference on Principles and Practice of Constraint Programming - Aula magna, Perugia, Italy
    Duration: 12 Sept 201116 Sept 2011

    Publication series

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


    Conference17th International Conference on Principles and Practice of Constraint Programming
    Abbreviated titleCP 2011
    Internet address


    • Automatic Generation
    • Constraint satisfaction problems
    • Modelling techniques
    • Subtrees
    • Symmetry-breaking


    Dive into the research topics of 'Automatic generation of constraints for partial symmetry breaking'. Together they form a unique fingerprint.

    Cite this