×

Search combinators. (English) Zbl 1309.90090

Summary: 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.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Baatar, D., Boland, N., Brand, S., Stuckey, P.J. (2011). CP and IP approaches to cancer radiotherapy delivery optimization. Constraints, 16(2), 173–194. · Zbl 1213.90271
[2] Boussemart, F., Hemery, F., Lecoutre, C., Sais, L. (2004). Boosting systematic search by weighting constraints. In R.L. de Mántaras, & L. Saitta (Eds.), Proceedings of the 16th Eureopean conference on artificial intelligence, ECAI’2004 (pp. 146–150). IOS Press.
[3] Choi, C.W., Henz, M., Ng, K.B. (2001). A compositional framework for search. In Proceedings of CICLOPS: C olloquium on implementation of constraint and logic p rogramming systems, appeared as technical report TR-CS-003/2001. New Mexico State University. · Zbl 1067.68621
[4] Cook, W.R. (1989). A denotational semantics of inheritance. Ph.D. thesis, Brown University.
[5] Cremet, V., Garillot, F., Lenglet, S., Odersky, M. (2006). A core calculus for scala type checking. In R. Kralovic, & P. Urzyczyn (Eds.), Mathematical foundations of computer science 2006, 31st international symposium, MFCS 2006. LNCS (Vol. 4162, pp. 1–23). Springer. · Zbl 1132.68320
[6] Desouter, B. (2012). Modular search heuristics in scala. Master’s thesis, Ghent University (in Dutch).
[7] Hamadi, Y., Monfroy, E., Saubion, F. (Eds.) (2012). Autonomous search. Springer.
[8] Harvey, W.D., & Ginsberg, M.L. (1995). Limited discrepancy search. In Proceedings of the fourteenth international joint conference on artificial intelligence, IJCAI 95 (pp. 607–613). Morgan Kauufmann.
[9] IBM Corporation (2011). IBM ILOG CP optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-cp-optimizer/ . Accessed November 2012
[10] Kiczales, G., Lamping, J., Menhdhekar, A., Maeda, C., Lopes, C., Loingtier, J., Irwin, J. (1997). Aspect-oriented programming. In ECOOP’97 - object-oriented programming, 11th European conference. LNCS (Vol. 1241, pp. 220–242). Springer.
[11] Korf, R.E. (1985). Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence, 27, 97–109. · Zbl 0573.68030
[12] Kuchcinski, K., & Szymanek, R. (2012). JaCoP - Java constraint programming solver. http://www.jacop.eu/ . Accessed November 2012
[13] Laburthe, F., & Caseau, Y. (2002). SALSA: a language for search algorithms. Constraints, 7(3), 255–288. · Zbl 1020.68028
[14] Marriott, K., Nethercote, N., Rafeh, R., Stuckey, P., Garcia de la Banda, M., Wallace, M. (2008). The design of the zinc modelling language. Constraints, 13(3), 229–267. · Zbl 1146.68352
[15] Nethercote, N., Stuckey, P., Becket, R., Brand, S., Duck, G., Tack, G. (2007). Minizinc: towards a standard CP modelling language. In C. Bessiere (Ed.), Thirteenth international conference on principles and practice of constraint programming. LNCS (Vol. 4741, pp. 529–543). Springer.
[16] Perron, L. (1999). Search procedures and parallelism in constraint programming. In J. Jaffar (Ed.), Fifth international conference on principles and practice of constraint programming. LNCS (Vol. 1713, pp. 346–360). Springer.
[17] Rafeh, R., Marriott, K., de la Banda, M.G., Nethercote, N., Wallace, M. (2008). Adding search to zinc. In P.J. Stuckey (Ed.), Fourteenth international conference on principles and practice of constraint programming. LNCS (Vol. 5202, pp. 624–629). Springer. · Zbl 1146.68352
[18] Refalo, P. (2004). Impact-based search strategies for constraint programming. In M. Wallace (Ed.), Tenth international conference on principles and practice of constraint programming. LNCS (Vol. 3258, pp. 557–571). Springer. · Zbl 1152.68577
[19] Samulowitz, H., Tack, G., Fischer, J., Wallace, M., Stuckey, P. (2010). Towards a lightweight standard search language. In The 9th international workshop on constraint modelling and reformulation (ModRef). http://www.it.uu.se/research/group/astra/ModRef10/programme.html . Accessed November 2012
[20] Schimpf, J., & Shen, K. (2012). ECLiPSe – from LP to CLP. Theory and Practice of Logic Programming, 12(1–2), 127–156. · Zbl 1244.68020
[21] Schrijvers, T., Stuckey, P.J., Wadler, P. (2009). Monadic constraint programming. Journal of Functional Programming, 19(6), 663–697. · Zbl 1184.68166
[22] Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H., Stuckey, P. (2011). Search combinators. In J. Lee (Ed.), Seventeenth international conference on principles and practice of constraint programming. LNCS (Vol. 6876, pp. 774–788). Springer. · Zbl 1309.90090
[23] Schrijvers, T., Triska, M., Demoen, B. (2012). Tor: extensible search with hookable disjunction. In Principles and practice of declarative programming (PPDP’12). ACM.
[24] Schulte, C. (1997). Programming constraint inference engines. In G. Smolka (Ed.), Third international conference on principles and practice of constraint programming. LNCS (Vol. 1330, pp. 519–533). Springer
[25] Schulte, C., et al. (2009). Gecode, the generic constraint development environment. http://www.gecode.org/ . Accessed November 2012
[26] Sellmann, M., & Kadioglu, S. (2008). Dichotomic search protocols for constrained optimization. In P.J. Stuckey (Ed.), Fourteenth international conference on principles and practice of constraint programming. LNCS (Vol. 5202, pp. 251–265). Springer.
[27] Smolka, G. (1995). The Oz programming model. In J. van Leeuwen (Ed.), Computer science today. LNCS (Vol. 1000, pp. 324–343). Springer.
[28] Swedish Institute of Computer Science (2008). SICStus prolog. http://www.sics.se/isl/sicstuswww/site/ . Accessed November 2012
[29] Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. MIT Press. · Zbl 1153.90582
[30] Van Hentenryck, P., & Michel, L. (2006). Nondeterministic control for hybrid search. Constraints, 11(4), 353–373. · Zbl 1112.68039
[31] Van Hentenryck, P., Perron, L., Puget, J.F. (2000). Search and strategies in OPL. ACM Transactions on Computational Logic, 1(2), 285–315. · Zbl 1365.90281
[32] Wielemaker, J., Schrijvers, T., Triska, M., Lager, T. (2012). SWI-Prolog. Theory and Practice of Logic Programming, 12(1–2), 67–96. · Zbl 1244.68023
[33] Zhou, N.F. (2012). The language features and architecture of B-Prolog. Theory and Practice of Logic Programming, 12(1–2), 189–218. · Zbl 1244.68024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.