Search combinators

DOI10.1007/S10601-012-9137-8MaRDI QIDQ487659zbMATHOpenAlexFDO

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

Publication date 22 January 2015

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.1095

zbMATH Keywords

modularityimplementationmodeling languagesearch heuristics

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

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.

Recommendations

• An introduction to search combinators
• scientific article; zbMATH DE number 41347
• Publication:4207884
• Random search on comb
• Search mechanisms
• Search
• scientific article; zbMATH DE number 1226090
• Combinatorial search: from algorithms to systems

Cites work

• scientific article; zbMATH DE number 2084709 (Why is no real title available?)
• A Core Calculus for Scala Type Checking
• CP and IP approaches to cancer radiotherapy delivery optimization
• Depth-first iterative-deepening: An optimal admissible tree search
• Monadic constraint programming
• Nondeterministic control for hybrid search
• Parallel Local Search in Comet
• Principles and Practice of Constraint Programming – CP 2004
• SALSA: a language for search algorithms
• SWI-Prolog
• Search and strategies in OPL
• Search combinators
• The design of the zinc modelling language
• The language features and architecture of B-Prolog
• \(\text{ECL}^{\text{i}}\text{PS}^{\text{e}}\) -- from LP to CLP

Cited in

(10)

• Contraint-based combinators for local search
• Des explications pour reconnaître et exploiter les structures cachées d'un problème combinatoire
• MiniCP: a lightweight solver for constraint programming
• A microkernel architecture for constraint programming
• An introduction to search combinators
• Tools for modeling and solving search problems
• Modular lazy search for constraint satisfaction problems
• Combining Heuristics for Configuration Problems Using Answer Set Programming
• Principles and Practice of Constraint Programming – CP 2004
• Search combinators

Describes a project that uses

Uses Software

• SALSA
• COMET
• MiniZinc
• Gecode
• JaCoP
• Oz
• B-Prolog
• Zinc
• SICStus
• SWI-Prolog
• OPL

This page was built for publication: Search combinators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q487659)