×

zbMATH — the first resource for mathematics

From rules to constraint programs with the Rules2CP modelling language. (English) Zbl 1248.68453
Oddi, Angelo (ed.) et al., Recent advances in constraints. 13th annual ERCIM international workshop on constraint solving and constraint logic programming, CSCLP 2008, Rome, Italy, June 18–20, 2008. Revised selected papers. Berlin: Springer (ISBN 978-3-642-03250-9/pbk). Lecture Notes in Computer Science 5655. Lecture Notes in Artificial Intelligence, 66-83 (2009).
Summary: In this paper, we present a rule-based modelling language for constraint programming, called Rules2CP. Unlike other modelling languages, Rules2CP adopts a single knowledge representation paradigm based on rules without recursion, and a restricted set of data structures based on records and enumerated lists given with iterators. We show that this is sufficient to model constraint satisfaction problems, together with search strategies where search trees are expressed by logical formulae, and heuristic choice criteria are defined by preference orderings on variables and formulae. We describe the compilation of Rules2CP statements to constraint programs over finite domains, by a term rewriting system and partial evaluation. We prove the confluence of these transformations and provide a complexity bound on the size of the generated programs. The expressiveness of Rules2CP is illustrated first with simple examples, and then with a complete library for packing problems, called PKML, which, in addition to pure bin packing and bin design problems, can deal with common sense rules about weights, stability, as well as specific packing business rules. The performances of both the compiler and the generated code are evaluated on Korf’s benchmarks of optimal rectangle packing problems.
For the entire collection see [Zbl 1168.68004].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Van Hentenryck, P.: The OPL Optimization programming Language. MIT Press, Cambridge (1999)
[2] Hentenryck, P.V., Perron, L., Puget, J.F.: Search and strategies in opl. ACM Transactions on Compututational Logic 1, 285–320 (2000) · Zbl 1365.90281 · doi:10.1145/359496.359529
[3] Rafeh, R., de la Banda, M.G., Marriott, K., Wallace, M.: From Zinc to design model. In: Hanus, M. (ed.) PADL 2007. LNCS, vol. 4354, pp. 215–229. Springer, Heidelberg (2006) · Zbl 1146.68352 · doi:10.1007/978-3-540-69611-7_14
[4] de la Banda, M.G., Marriott, K., Rafeh, R., Wallace, M.: The modelling language Zinc. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 700–705. Springer, Heidelberg (2006) · Zbl 05323514 · doi:10.1007/11889205_54
[5] Frisch, A.M., Harvey, W., Jefferson, C., Martinez-Hernandez, B., Miguel, I.: Essence: A constraint language for specifying combinatorial problems. Constraints 13, 268–306 (2008) · Zbl 1147.68424 · doi:10.1007/s10601-008-9047-y
[6] Group, B.R.: The business rules manifesto Business Rules Group (2003), http://www.businessrulesgroup.org/brmanifesto.htm
[7] Korf, R.E.: Optimal rectangle packing: New results. In: ICAPS, pp. 142–149 (2004)
[8] Haemmerlé, R., Fages, F.: Modules for prolog revisited. In: Etalle, S., Truszczyński, M. (eds.) ICLP 2006. LNCS, vol. 4079, pp. 41–55. Springer, Heidelberg (2006) · Zbl 1131.68378 · doi:10.1007/11799573_6
[9] Van Hentenryck, P.: Constraint satisfaction in Logic Programming. MIT Press, Cambridge (1989)
[10] Huang, J., Darwiche, A.: The language of search. Journal of Artificial Intelligence Research 29, 191–219 (2007) · Zbl 1183.68232
[11] Apt, K., Wallace, M.: Constraint Logic Programming using Eclipse. Cambridge University Press, Cambridge (2006) · Zbl 1119.68044 · doi:10.1017/CBO9780511607400
[12] Carlsson, M., et al.: SICStus Prolog User’s Manual. Swedish Institute of Computer Science, 4th edn. (2007), ISBN 91-630-3648-7
[13] Fages, F., Soliman, S., Coolen, R.: CLPGUI: a generic graphical user interface for constraint logic programming. Journal of Constraints, Special Issue on User-Interaction in Constraint Satisfaction 9, 241–262 (2004)
[14] Fages, F., Martin, J.: From rules to constraint programs with the Rules2CP modelling language. INRIA Research Report RR-6495, Institut National de Recherche en Informatique (2008) · Zbl 1248.68453
[15] Rosen, B.: Tree-manipulating systems and Church-Rosser theorems. Journal of the ACM 20, 160–187 (1973) · Zbl 0267.68013 · doi:10.1145/321738.321750
[16] Carlsson, M., Beldiceanu, N., Martin, J.: A geometric constraint over k-dimensional objects and shapes subject to business rules. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 220–234. Springer, Heidelberg (2008) · Zbl 05372881 · doi:10.1007/978-3-540-85958-1_15
[17] Beldiceanu, N., Carlsson, M., Poder, E., Sadek, R., Truchet, C.: A generic geometrical constraint kernel in space and time for handling polymorphic k-dimensional objects. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 180–194. Springer, Heidelberg (2007); SICS Technical Report T2007:08, http://www.sics.se/libindex.html · Zbl 05318815 · doi:10.1007/978-3-540-74970-7_15
[18] Allen, J.: Time and time again: The many ways to represent time. International Journal of Intelligent System 6 (1991) · doi:10.1002/int.4550060403
[19] Randell, D., Cui, Z., Cohn, A.: A spatial logic based on regions and connection. In: Nebel, B., Rich, C., Swartout, W.R. (eds.) Proc. of 2nd International Conference on Knowledge Representation and reasoning KR 1992, pp. 165–176. Morgan Kaufmann, San Francisco (1992)
[20] Carpenter, H., Dowsland, W.: Practical consideration of the pallet loading problem. Journal of the Operations Research Society 36, 489–497 (1985) · Zbl 0566.90052 · doi:10.1057/jors.1985.84
[21] Simonis, H., O’Sullivan, B.: Using global constraints for rectangle packing. In: Proceedings of the first Workshop on Bin Packing and Placement Constraints BPPC 2008, associated to CPAIOR 2008 (2008)
[22] Jaffar, J., Lassez, J.L.: Constraint logic programming. In: Proceedings of the 14th ACM Symposium on Principles of Programming Languages, pp. 111–119. ACM, Munich (1987)
[23] Balland, E., Brauner, P., Kopetz, R., Moreau, P.E., Reilles, A.: Tom: Piggybacking rewriting on java. In: Baader, F. (ed.) RTA 2007. LNCS, vol. 4533, pp. 36–47. Springer, Heidelberg (2007) · Zbl 05222802 · doi:10.1007/978-3-540-73449-9_5
[24] Fages, F., Coquery, E.: Typing constraint logic programs. Journal of Theory and Practice of Logic Programming 1, 751–777 (2001) · Zbl 1066.68514 · doi:10.1017/S1471068401001120
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.