A method for detecting symmetries in constraint models and its generalisation

Christopher David Mears, Maria Jose Garcia De La Banda, Mark Wallace, Bart Demoen

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    The symmetries that appear in many constraint problems can be used to significantly speed up the search for solutions to these problems. While the accurate detection of symmetries in instances of a given constraint problem is possible, current methods tend to be impractical for real-sized instances. On the other hand, methods capable of detecting properties for a problem model ? and thus all its instances ? are efficient but not accurate enough. This paper presents a new method for inferring symmetries in constraint satisfaction models that combines the high accuracy of instance-based methods with the efficiency of model-based methods; the key insight is that symmetries detected for small instances of the model can be generalised to the model itself. Experimental evaluation shows that this approach is able to find all symmetries in almost all the benchmark problems used. The generality of our method is then illustrated by showing how it can be applied to infer other properties.
    Original languageEnglish
    Pages (from-to)235 - 273
    Number of pages39
    JournalConstraints
    Volume20
    Issue number2
    DOIs
    Publication statusPublished - 2015

    Cite this

    @article{b3ca13239d3d4547a4a596244ab522f3,
    title = "A method for detecting symmetries in constraint models and its generalisation",
    abstract = "The symmetries that appear in many constraint problems can be used to significantly speed up the search for solutions to these problems. While the accurate detection of symmetries in instances of a given constraint problem is possible, current methods tend to be impractical for real-sized instances. On the other hand, methods capable of detecting properties for a problem model ? and thus all its instances ? are efficient but not accurate enough. This paper presents a new method for inferring symmetries in constraint satisfaction models that combines the high accuracy of instance-based methods with the efficiency of model-based methods; the key insight is that symmetries detected for small instances of the model can be generalised to the model itself. Experimental evaluation shows that this approach is able to find all symmetries in almost all the benchmark problems used. The generality of our method is then illustrated by showing how it can be applied to infer other properties.",
    author = "Mears, {Christopher David} and {Garcia De La Banda}, {Maria Jose} and Mark Wallace and Bart Demoen",
    year = "2015",
    doi = "10.1007/s10601-014-9175-5",
    language = "English",
    volume = "20",
    pages = "235 -- 273",
    journal = "Constraints",
    issn = "1383-7133",
    publisher = "Springer-Verlag London Ltd.",
    number = "2",

    }

    A method for detecting symmetries in constraint models and its generalisation. / Mears, Christopher David; Garcia De La Banda, Maria Jose; Wallace, Mark; Demoen, Bart.

    In: Constraints, Vol. 20, No. 2, 2015, p. 235 - 273.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - A method for detecting symmetries in constraint models and its generalisation

    AU - Mears, Christopher David

    AU - Garcia De La Banda, Maria Jose

    AU - Wallace, Mark

    AU - Demoen, Bart

    PY - 2015

    Y1 - 2015

    N2 - The symmetries that appear in many constraint problems can be used to significantly speed up the search for solutions to these problems. While the accurate detection of symmetries in instances of a given constraint problem is possible, current methods tend to be impractical for real-sized instances. On the other hand, methods capable of detecting properties for a problem model ? and thus all its instances ? are efficient but not accurate enough. This paper presents a new method for inferring symmetries in constraint satisfaction models that combines the high accuracy of instance-based methods with the efficiency of model-based methods; the key insight is that symmetries detected for small instances of the model can be generalised to the model itself. Experimental evaluation shows that this approach is able to find all symmetries in almost all the benchmark problems used. The generality of our method is then illustrated by showing how it can be applied to infer other properties.

    AB - The symmetries that appear in many constraint problems can be used to significantly speed up the search for solutions to these problems. While the accurate detection of symmetries in instances of a given constraint problem is possible, current methods tend to be impractical for real-sized instances. On the other hand, methods capable of detecting properties for a problem model ? and thus all its instances ? are efficient but not accurate enough. This paper presents a new method for inferring symmetries in constraint satisfaction models that combines the high accuracy of instance-based methods with the efficiency of model-based methods; the key insight is that symmetries detected for small instances of the model can be generalised to the model itself. Experimental evaluation shows that this approach is able to find all symmetries in almost all the benchmark problems used. The generality of our method is then illustrated by showing how it can be applied to infer other properties.

    UR - http://goo.gl/alBov3

    U2 - 10.1007/s10601-014-9175-5

    DO - 10.1007/s10601-014-9175-5

    M3 - Article

    VL - 20

    SP - 235

    EP - 273

    JO - Constraints

    JF - Constraints

    SN - 1383-7133

    IS - 2

    ER -