Advanced search
1 file | 191.45 KB
Author
Organization
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.
Keywords
programming language, modeling language, constraint programming, search heuristics, combinatorial optimization, search algorithms, mixins, domain-specific language, combinatorial problems, modularity

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 191.45 KB

Citation

Please use this url to cite or link to this publication:

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.
@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},
}

Altmetric
View in Altmetric