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

    4 Citations (Scopus)

    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