Learning when to use lazy learning in constraint solving

Ian P. Gent, Chris Jefferson, Lars Kotthoff, Ian Miguel, Neil C. A. Moore, Peter Nightingale, Karen Petrie

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

    13 Citations (Scopus)

    Abstract

    Learning in the context of constraint solving is a technique by which previously unknown constraints are uncovered during search and used to speed up subsequent search. Recently, lazy learning, similar to a successful idea from satisfiability modulo theories solvers, has been shown to be an effective means of incorporating constraint learning into a solver. Although a powerful technique to reduce search in some circumstances, lazy learning introduces a substantial overhead, which can outweigh its benefits. Hence, it is desirable to know beforehand whether or not it is expected to be useful. We approach this problem using machine learning (ML). We show that, in the context of a large benchmark set, standard ML approaches can be used to learn a simple, cheap classifier which performs well in identifying instances on which lazy learning should or should not be used. Furthermore, we demonstrate significant performance improvements of a system using our classifier and the lazy learning and standard constraint solvers over a standard solver. Through rigorous cross-validation across the different problem classes in our benchmark set, we show the general applicability of our learned classifier.
    Original languageEnglish
    Title of host publicationECAI 2010
    Subtitle of host publication19th European Conference on Artificial Intelligence, 16-20 August 2010, Lisbon, Portugal - including Prestigious Applications of Artificial Intelligence (PAIS-2010). Proceedings
    EditorsHelder Coelho, Rudi Studer, Michael Wooldridge
    Place of PublicationAmsterdam
    PublisherIOS Press
    Pages873-878
    Number of pages6
    ISBN (Electronic)9781607506065
    ISBN (Print)9781607506058
    DOIs
    Publication statusPublished - 2010
    Event19th European Conference on Artificial Intelligence - University of Lisbon, Faculty of Science, Lisbon, Portugal
    Duration: 16 Aug 201020 Aug 2010
    http://ecai2010.appia.pt/

    Publication series

    NameFrontiers in artificial intelligence and applications
    PublisherIOS Press
    Volume215
    ISSN (Print)0922-6389

    Conference

    Conference19th European Conference on Artificial Intelligence
    Abbreviated titleECAI 2010
    CountryPortugal
    CityLisbon
    Period16/08/1020/08/10
    Internet address

    Fingerprint Dive into the research topics of 'Learning when to use lazy learning in constraint solving'. Together they form a unique fingerprint.

    Cite this