Ghent University Academic Bibliography

Advanced

Search combinators

Tom Schrijvers UGent, Guido Tack, Pieter Wuille UGent, Horst Samulowitz and Peter J Stuckey (2013) CONSTRAINTS. 18(2). p.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 unex- plored. 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.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
heuristics, constraint programming, domain specific languages, modularity, tree search, MODELING LANGUAGE, CONSTRAINT, PROLOG, ZINC
journal title
CONSTRAINTS
Constraints
volume
18
issue
2
pages
269 - 305
Web of Science type
Article
Web of Science id
000316021000006
JCR category
COMPUTER SCIENCE, THEORY & METHODS
JCR impact factor
1.152 (2013)
JCR rank
31/102 (2013)
JCR quartile
2 (2013)
ISSN
1383-7133
DOI
10.1007/s10601-012-9137-8
language
English
UGent publication?
yes
classification
A1
copyright statement
I have transferred the copyright for this publication to the publisher
id
3063614
handle
http://hdl.handle.net/1854/LU-3063614
date created
2012-12-01 11:09:32
date last changed
2014-12-18 15:09:46
@article{3063614,
  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 unex- plored.
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.},
  author       = {Schrijvers, Tom and Tack, Guido and Wuille, Pieter and Samulowitz, Horst and Stuckey, Peter J},
  issn         = {1383-7133},
  journal      = {CONSTRAINTS},
  keyword      = {heuristics,constraint programming,domain specific languages,modularity,tree search,MODELING LANGUAGE,CONSTRAINT,PROLOG,ZINC},
  language     = {eng},
  number       = {2},
  pages        = {269--305},
  title        = {Search combinators},
  url          = {http://dx.doi.org/10.1007/s10601-012-9137-8},
  volume       = {18},
  year         = {2013},
}

Chicago
Schrijvers, Tom, Guido Tack, Pieter Wuille, Horst Samulowitz, and Peter J Stuckey. 2013. “Search Combinators.” Constraints 18 (2): 269–305.
APA
Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H., & Stuckey, P. J. (2013). Search combinators. CONSTRAINTS, 18(2), 269–305.
Vancouver
1.
Schrijvers T, Tack G, Wuille P, Samulowitz H, Stuckey PJ. Search combinators. CONSTRAINTS. 2013;18(2):269–305.
MLA
Schrijvers, Tom, Guido Tack, Pieter Wuille, et al. “Search Combinators.” CONSTRAINTS 18.2 (2013): 269–305. Print.