Search combinators

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

doi:10.1007/978-3-642-23786-7_58

Search combinators

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

15 Citations (Scopus)

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 performance 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 developer 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.

Original language	English
Title of host publication	Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming
Editors	Jimmy Lee
Place of Publication	Berlin Germany
Publisher	Springer-Verlag London Ltd.
Pages	774-788
Number of pages	15
ISBN (Print)	9783642237850
DOIs	https://doi.org/10.1007/978-3-642-23786-7_58
Publication status	Published - 2011
Externally published	Yes
Event	International Conference on Principles and Practice of Constraint Programming 2011 - Perugia, Italy Duration: 12 Sept 2011 → 16 Sept 2011 Conference number: 17th http://www.dmi.unipg.it/cp2011/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6876 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	International Conference on Principles and Practice of Constraint Programming 2011
Abbreviated title	CP 2011
Country/Territory	Italy
City	Perugia
Period	12/09/11 → 16/09/11
Internet address	http://www.dmi.unipg.it/cp2011/

Access to Document

10.1007/978-3-642-23786-7_58

Cite this

Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H., & Stuckey, P. J. (2011). Search combinators. In J. Lee (Ed.), Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming (pp. 774-788). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6876 LNCS). Springer-Verlag London Ltd.. https://doi.org/10.1007/978-3-642-23786-7_58

Schrijvers, Tom ; Tack, Guido ; Wuille, Pieter et al. / Search combinators. Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming. editor / Jimmy Lee. Berlin Germany : Springer-Verlag London Ltd., 2011. pp. 774-788 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8a148919bb064f80bfe34ffffdc076c7,

title = "Search combinators",

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 performance 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 developer 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 = "Tom Schrijvers and Guido Tack and Pieter Wuille and Horst Samulowitz and Stuckey, {Peter J.}",

year = "2011",

doi = "10.1007/978-3-642-23786-7_58",

language = "English",

isbn = "9783642237850",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag London Ltd.",

pages = "774--788",

editor = "Jimmy Lee",

booktitle = "Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming",

address = "Germany",

note = "International Conference on Principles and Practice of Constraint Programming 2011, CP 2011 ; Conference date: 12-09-2011 Through 16-09-2011",

url = "http://www.dmi.unipg.it/cp2011/",

}

Schrijvers, T, Tack, G, Wuille, P, Samulowitz, H & Stuckey, PJ 2011, Search combinators. in J Lee (ed.), Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6876 LNCS, Springer-Verlag London Ltd., Berlin Germany, pp. 774-788, International Conference on Principles and Practice of Constraint Programming 2011, Perugia, Italy, 12/09/11. https://doi.org/10.1007/978-3-642-23786-7_58

Search combinators. / Schrijvers, Tom; Tack, Guido; Wuille, Pieter et al.
Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming. ed. / Jimmy Lee. Berlin Germany: Springer-Verlag London Ltd., 2011. p. 774-788 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6876 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Search combinators

AU - Schrijvers, Tom

AU - Tack, Guido

AU - Wuille, Pieter

AU - Samulowitz, Horst

AU - Stuckey, Peter J.

N1 - Conference code: 17th

PY - 2011

Y1 - 2011

N2 - 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 performance 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 developer 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.

AB - 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 performance 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 developer 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.

UR - http://www.scopus.com/inward/record.url?scp=80052987896&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-23786-7_58

DO - 10.1007/978-3-642-23786-7_58

M3 - Conference Paper

SN - 9783642237850

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 774

EP - 788

BT - Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming

A2 - Lee, Jimmy

PB - Springer-Verlag London Ltd.

CY - Berlin Germany

T2 - International Conference on Principles and Practice of Constraint Programming 2011

Y2 - 12 September 2011 through 16 September 2011

ER -

Schrijvers T, Tack G, Wuille P, Samulowitz H, Stuckey PJ. Search combinators. In Lee J, editor, Proceedings of the 17th International Conference on the Principles and Practice of Constraint Programming. Berlin Germany: Springer-Verlag London Ltd. 2011. p. 774-788. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-23786-7_58

Search combinators

Abstract

Publication series

Conference

Access to Document

Other files and links

Research output

Search combinators

Cite this