Ghent University Academic Bibliography

Advanced

Search combinators

Tom Schrijvers UGent, Guido Tack, Pieter Wuille, Horst Samulowitz and Peter J Stuckey (2011) Lecture Notes in Computer Science. 6876. p.774-788
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 low-level programming language and modeling search becomes unwieldy. As a result, major improvements in perfor- mance may remain unexplored. This paper introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple search language (high- level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). Search combinators allow one to define application-tailored strategies from a small set of primitives, resulting in a rich search language for the user and a low implementation cost for the de- veloper of a constraint solver. The paper 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
conference
publication status
published
subject
keyword
programming language, modeling language, constraint programming, search heuristics, combinatorial optimization, search algorithms, mixins, domain-specific language, combinatorial problems, modularity
in
Lecture Notes in Computer Science
Lect. Notes Comput. Sci.
editor
Jimmy Lee
volume
6876
issue title
Principles and practice of constraint programming : CP 2011
pages
774 - 788
publisher
Springer
place of publication
Berlin, Germany
conference name
17th International conference on Principles and Practice of Constraint Programming (CP 2011)
conference location
Perugia, Itlay
conference start
2011-09-12
conference end
2011-09-16
ISSN
0302-9743
ISBN
9783642237867
9783642237850
DOI
10.1007/978-3-642-23786-7_58
language
English
UGent publication?
yes
classification
C1
copyright statement
I have transferred the copyright for this publication to the publisher
VABB id
c:vabb:339827
VABB type
VABB-5
id
1255570
handle
http://hdl.handle.net/1854/LU-1255570
date created
2011-06-07 09:40:17
date last changed
2017-01-02 09:52:57
@inproceedings{1255570,
  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 low-level programming language and modeling search becomes unwieldy. As a result, major improvements in perfor- mance may remain unexplored.
This paper introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple search language (high- level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). Search combinators allow one to define application-tailored strategies from a small set of primitives, resulting in a rich search language for the user and a low implementation cost for the de- veloper of a constraint solver. The paper 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},
  booktitle    = {Lecture Notes in Computer Science},
  editor       = {Lee, Jimmy},
  isbn         = {9783642237867},
  issn         = {0302-9743},
  keyword      = {programming language,modeling language,constraint programming,search heuristics,combinatorial optimization,search algorithms,mixins,domain-specific language,combinatorial problems,modularity},
  language     = {eng},
  location     = {Perugia, Itlay},
  pages        = {774--788},
  publisher    = {Springer},
  title        = {Search combinators},
  url          = {http://dx.doi.org/10.1007/978-3-642-23786-7\_58},
  volume       = {6876},
  year         = {2011},
}

Chicago
Schrijvers, Tom, Guido Tack, Pieter Wuille, Horst Samulowitz, and Peter J Stuckey. 2011. “Search Combinators.” In Lecture Notes in Computer Science, ed. Jimmy Lee, 6876:774–788. Berlin, Germany: Springer.
APA
Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H., & Stuckey, P. J. (2011). Search combinators. In Jimmy Lee (Ed.), Lecture Notes in Computer Science (Vol. 6876, pp. 774–788). Presented at the 17th International conference on Principles and Practice of Constraint Programming (CP 2011), Berlin, Germany: Springer.
Vancouver
1.
Schrijvers T, Tack G, Wuille P, Samulowitz H, Stuckey PJ. Search combinators. In: Lee J, editor. Lecture Notes in Computer Science. Berlin, Germany: Springer; 2011. p. 774–88.
MLA
Schrijvers, Tom, Guido Tack, Pieter Wuille, et al. “Search Combinators.” Lecture Notes in Computer Science. Ed. Jimmy Lee. Vol. 6876. Berlin, Germany: Springer, 2011. 774–788. Print.