Search combinators

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

    Research output: Contribution to journalArticleResearchpeer-review

    20 Citations (Scopus)


    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
    Issue number2
    Publication statusPublished - 2013


    • Search heuristics
    • Modeling language
    • Modularity
    • Implementation
    • Search combinators

      Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H. & Stuckey, P. J., 2011, Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming. Lee, J. (ed.). Berlin Germany: Springer-Verlag London Ltd., p. 774-788 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6876 LNCS).

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

      15 Citations (Scopus)

    Cite this