Title: Search combinators
Authors: Schrijvers, Tom ×
Tack, Guido
Wuille, Pieter
Samulowitz, Horst
Stuckey, Peter J #
Issue Date: 2013
Publisher: Kluwer
Series Title: Constraints vol:18 issue:2 pages:269-305
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-specific 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.
ISSN: 1383-7133
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Non-KU Leuven Association publications
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
constraints2013.pdfarticle Published 399KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science