Search combinators

Tom Schrijvers, Guido Tack, Pieter Wuille, Horst Samulowitz, Peter J. Stuckey

    Research output: Contribution to journalArticleResearchpeer-review

    19 Citations (Scopus)

    Abstract

    The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specif ic language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver. The article discusses two modular implementation approaches and shows, by empirical evaluation, that search combinators can be implemented without overhead
    compared to a native, direct implementation in a constraint solver.
    Original languageEnglish
    Pages (from-to)269-305
    Number of pages37
    JournalConstraints
    Volume18
    Issue number2
    DOIs
    Publication statusPublished - 2013

    Keywords

    • Search heuristics
    • Modeling language
    • Modularity
    • Implementation

    Cite this

    Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H., & Stuckey, P. J. (2013). Search combinators. Constraints, 18(2), 269-305. https://doi.org/10.1007/s10601-012-9137-8