Search combinators

DOI10.1007/S10601-012-9137-8zbMATH Open1309.90090arXiv1203.1095OpenAlexW2914215093MaRDI QIDQ487659FDOQ487659

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)

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.

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

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

zbMATH Keywords

modularityimplementationmodeling languagesearch heuristics

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

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

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)