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

    Keywords

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

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

  • 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). Springer . https://doi.org/10.1007/978-3-642-23786-7_55