Automatic generation of constraints for partial symmetry breaking

Christopher Jefferson, Karen E. Petrie

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

    6 Citations (Scopus)

    Abstract

    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
    PublisherSpringer
    Pages729-743
    Number of pages15
    ISBN (Electronic)9783642237867
    ISBN (Print)9783642237850
    DOIs
    Publication statusPublished - 2011
    Event17th International Conference on Principles and Practice of Constraint Programming - Aula magna, Perugia, Italy
    Duration: 12 Sep 201116 Sep 2011
    http://www.dmi.unipg.it/cp2011/

    Publication series

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

    Conference

    Conference17th International Conference on Principles and Practice of Constraint Programming
    Abbreviated titleCP 2011
    CountryItaly
    CityPerugia
    Period12/09/1116/09/11
    Internet address

    Fingerprint

    Equivalence classes
    Constraint satisfaction problems
    Defects

    Keywords

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

    Cite this

    Jefferson, C., & Petrie, K. E. (2011). Automatic generation of constraints for partial symmetry breaking. In J. Lee (Ed.), Principles and practice of constraint programming - CP 2011: 7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings (pp. 729-743). (Lecture notes in computer science; Vol. 6876). Berlin: Springer . https://doi.org/10.1007/978-3-642-23786-7_55
    Jefferson, Christopher ; Petrie, Karen E. / Automatic generation of constraints for partial symmetry breaking. Principles and practice of constraint programming - CP 2011: 7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings. editor / Jimmy Lee. Berlin : Springer , 2011. pp. 729-743 (Lecture notes in computer science).
    @inproceedings{641e369963bf4aee8933e4c35ffb6bff,
    title = "Automatic generation of constraints for partial symmetry breaking",
    abstract = "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.",
    keywords = "Automatic Generation, Constraint satisfaction problems, Modelling techniques, Subtrees, Symmetry-breaking",
    author = "Christopher Jefferson and Petrie, {Karen E.}",
    year = "2011",
    doi = "10.1007/978-3-642-23786-7_55",
    language = "English",
    isbn = "9783642237850",
    series = "Lecture notes in computer science",
    publisher = "Springer",
    pages = "729--743",
    editor = "Jimmy Lee",
    booktitle = "Principles and practice of constraint programming - CP 2011",

    }

    Jefferson, C & Petrie, KE 2011, Automatic generation of constraints for partial symmetry breaking. in J Lee (ed.), Principles and practice of constraint programming - CP 2011: 7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings. Lecture notes in computer science, vol. 6876, Springer , Berlin, pp. 729-743, 17th International Conference on Principles and Practice of Constraint Programming , Perugia, Italy, 12/09/11. https://doi.org/10.1007/978-3-642-23786-7_55

    Automatic generation of constraints for partial symmetry breaking. / Jefferson, Christopher; Petrie, Karen E.

    Principles and practice of constraint programming - CP 2011: 7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings. ed. / Jimmy Lee. Berlin : Springer , 2011. p. 729-743 (Lecture notes in computer science; Vol. 6876).

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

    TY - GEN

    T1 - Automatic generation of constraints for partial symmetry breaking

    AU - Jefferson, Christopher

    AU - Petrie, Karen E.

    PY - 2011

    Y1 - 2011

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

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

    KW - Automatic Generation

    KW - Constraint satisfaction problems

    KW - Modelling techniques

    KW - Subtrees

    KW - Symmetry-breaking

    UR - http://www.scopus.com/inward/record.url?scp=80052986326&partnerID=8YFLogxK

    U2 - 10.1007/978-3-642-23786-7_55

    DO - 10.1007/978-3-642-23786-7_55

    M3 - Conference contribution

    AN - SCOPUS:80052986326

    SN - 9783642237850

    T3 - Lecture notes in computer science

    SP - 729

    EP - 743

    BT - Principles and practice of constraint programming - CP 2011

    A2 - Lee, Jimmy

    PB - Springer

    CY - Berlin

    ER -

    Jefferson C, Petrie KE. Automatic generation of constraints for partial symmetry breaking. In Lee J, editor, Principles and practice of constraint programming - CP 2011: 7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings. Berlin: Springer . 2011. p. 729-743. (Lecture notes in computer science). https://doi.org/10.1007/978-3-642-23786-7_55