Learning from learning solvers

Maxim Shishmarev, Christopher Mears, Guido Tack, Maria Garcia de la Banda

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    Abstract

    Modern constraint programming solvers incorporate SATstyle clause learning, where sets of domain restrictions that lead to failure are recorded as new clausal propagators. While this can yield dramatic reductions in search, there are also cases where clause learning does not improve or even hinders performance. Unfortunately, the reasons for these differences in behaviour are not well understood in practice. We aim to cast some light on the practical behaviour of learning solvers by profiling their execution. In particular, we instrument the learning solver Chuffed to produce a detailed record of its execution and extend a graphical profiling tool to appropriately display this information. Further, this profiler enables users to measure the impact of the learnt clauses by comparing Chuffed’s execution with that of a non-learning solver, and examining the points at which their behaviours diverge. We show that analysing a solver’s execution in this way can be useful not only to better understand its behaviour — opening what is typically a black box — but also to infer modifications to the original constraint model that can improve the performance of both learning and non-learning solvers.

    Original languageEnglish
    Title of host publicationPrinciples and Practice of Constraint Programming
    Subtitle of host publication22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings
    EditorsMichel Rueher
    Place of PublicationSwitzerland
    PublisherSpringer
    Pages455-472
    Number of pages18
    ISBN (Electronic)9783319449531
    ISBN (Print)9783319449524
    DOIs
    Publication statusPublished - 2016
    EventInternational Conference on Principles and Practice of Constraint Programming 2016 - Toulouse, France
    Duration: 5 Sep 20169 Sep 2016
    Conference number: 22d
    http://cp2016.a4cp.org/

    Publication series

    NameLecture Notes in Computer Science
    Volume9892
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceInternational Conference on Principles and Practice of Constraint Programming 2016
    Abbreviated titleCP 2016
    CountryFrance
    CityToulouse
    Period5/09/169/09/16
    Internet address

    Cite this

    Shishmarev, M., Mears, C., Tack, G., & Garcia de la Banda, M. (2016). Learning from learning solvers. In M. Rueher (Ed.), Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings (pp. 455-472). (Lecture Notes in Computer Science; Vol. 9892 ). Switzerland: Springer. https://doi.org/10.1007/978-3-319-44953-1_29
    Shishmarev, Maxim ; Mears, Christopher ; Tack, Guido ; Garcia de la Banda, Maria. / Learning from learning solvers. Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. editor / Michel Rueher. Switzerland : Springer, 2016. pp. 455-472 (Lecture Notes in Computer Science).
    @inproceedings{e683b7e43552469e932acb8f100d5fd7,
    title = "Learning from learning solvers",
    abstract = "Modern constraint programming solvers incorporate SATstyle clause learning, where sets of domain restrictions that lead to failure are recorded as new clausal propagators. While this can yield dramatic reductions in search, there are also cases where clause learning does not improve or even hinders performance. Unfortunately, the reasons for these differences in behaviour are not well understood in practice. We aim to cast some light on the practical behaviour of learning solvers by profiling their execution. In particular, we instrument the learning solver Chuffed to produce a detailed record of its execution and extend a graphical profiling tool to appropriately display this information. Further, this profiler enables users to measure the impact of the learnt clauses by comparing Chuffed’s execution with that of a non-learning solver, and examining the points at which their behaviours diverge. We show that analysing a solver’s execution in this way can be useful not only to better understand its behaviour — opening what is typically a black box — but also to infer modifications to the original constraint model that can improve the performance of both learning and non-learning solvers.",
    author = "Maxim Shishmarev and Christopher Mears and Guido Tack and {Garcia de la Banda}, Maria",
    year = "2016",
    doi = "10.1007/978-3-319-44953-1_29",
    language = "English",
    isbn = "9783319449524",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "455--472",
    editor = "Michel Rueher",
    booktitle = "Principles and Practice of Constraint Programming",

    }

    Shishmarev, M, Mears, C, Tack, G & Garcia de la Banda, M 2016, Learning from learning solvers. in M Rueher (ed.), Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9892 , Springer, Switzerland, pp. 455-472, International Conference on Principles and Practice of Constraint Programming 2016, Toulouse, France, 5/09/16. https://doi.org/10.1007/978-3-319-44953-1_29

    Learning from learning solvers. / Shishmarev, Maxim; Mears, Christopher; Tack, Guido; Garcia de la Banda, Maria.

    Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. ed. / Michel Rueher. Switzerland : Springer, 2016. p. 455-472 (Lecture Notes in Computer Science; Vol. 9892 ).

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    TY - GEN

    T1 - Learning from learning solvers

    AU - Shishmarev, Maxim

    AU - Mears, Christopher

    AU - Tack, Guido

    AU - Garcia de la Banda, Maria

    PY - 2016

    Y1 - 2016

    N2 - Modern constraint programming solvers incorporate SATstyle clause learning, where sets of domain restrictions that lead to failure are recorded as new clausal propagators. While this can yield dramatic reductions in search, there are also cases where clause learning does not improve or even hinders performance. Unfortunately, the reasons for these differences in behaviour are not well understood in practice. We aim to cast some light on the practical behaviour of learning solvers by profiling their execution. In particular, we instrument the learning solver Chuffed to produce a detailed record of its execution and extend a graphical profiling tool to appropriately display this information. Further, this profiler enables users to measure the impact of the learnt clauses by comparing Chuffed’s execution with that of a non-learning solver, and examining the points at which their behaviours diverge. We show that analysing a solver’s execution in this way can be useful not only to better understand its behaviour — opening what is typically a black box — but also to infer modifications to the original constraint model that can improve the performance of both learning and non-learning solvers.

    AB - Modern constraint programming solvers incorporate SATstyle clause learning, where sets of domain restrictions that lead to failure are recorded as new clausal propagators. While this can yield dramatic reductions in search, there are also cases where clause learning does not improve or even hinders performance. Unfortunately, the reasons for these differences in behaviour are not well understood in practice. We aim to cast some light on the practical behaviour of learning solvers by profiling their execution. In particular, we instrument the learning solver Chuffed to produce a detailed record of its execution and extend a graphical profiling tool to appropriately display this information. Further, this profiler enables users to measure the impact of the learnt clauses by comparing Chuffed’s execution with that of a non-learning solver, and examining the points at which their behaviours diverge. We show that analysing a solver’s execution in this way can be useful not only to better understand its behaviour — opening what is typically a black box — but also to infer modifications to the original constraint model that can improve the performance of both learning and non-learning solvers.

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

    UR - http://link.springer.com/book/10.1007/978-3-319-44953-1

    U2 - 10.1007/978-3-319-44953-1_29

    DO - 10.1007/978-3-319-44953-1_29

    M3 - Conference Paper

    SN - 9783319449524

    T3 - Lecture Notes in Computer Science

    SP - 455

    EP - 472

    BT - Principles and Practice of Constraint Programming

    A2 - Rueher, Michel

    PB - Springer

    CY - Switzerland

    ER -

    Shishmarev M, Mears C, Tack G, Garcia de la Banda M. Learning from learning solvers. In Rueher M, editor, Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Switzerland: Springer. 2016. p. 455-472. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-44953-1_29