×

zbMATH — the first resource for mathematics

The design of the zinc modelling language. (English) Zbl 1146.68352
Summary: Zinc is a new modelling language developed as part of the G12 project. It has four important characteristics. First, Zinc allows specification of models using a natural mathematical-like notation. To do so it supports overloaded functions and predicates and automatic coercion and provides arithmetic, finite domain and set constraints. Second, while Zinc is a relatively simple and small language, it can be readily extended to different application areas by means of powerful language constructs such as user-defined predicates and functions and constrained types. Third, Zinc provides sophisticated type and instantiation checking which allows early detection of errors in models. Finally, perhaps the main novelty in Zinc is that it is designed to support a modelling methodology in which the same conceptual model can be automatically mapped into different design models, thus allowing modellers to easily “plug and play” with different solving techniques and so choose the most appropriate for that problem. We describe in detail the various language features of Zinc and the many trade-offs we faced in its design.

MSC:
68N15 Theory of programming languages
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apt, K., & Wallace, M. (2007). Constraint logic programming using ECLiPSe. Cambridge: Cambridge University Press. · Zbl 1119.68044
[2] Bowen, J. P. (1996). Formal specification and documentation using Z: A case study approach. Boston: International Thomson Computer Press.
[3] Brand, S., Naroditskaya, N., Quimper, C.-G., Stuckey, P. J., & Walsh, T. (2007). Encodings of the sequence constaint. In Proceedings of the 13th international conference on principles and practice of constraint programming (CP2007), Providence, Rhode Island, USA (September).
[4] Demoen, B., García de la Banda, M., Harvey, W., Marriott, K., & Stuckey, P. J. (1999). An overview of HAL. In Jaffar, J. (ed.), Proceedings of the fourth international conference on principles and practices of constraint programming, LNCS, (pp. 174–188). New York: Springer. · Zbl 1083.68019
[5] DIMACS, (1993). Satisfiability suggested format. ftp://dimacs.rutgers.edu/pub/challenge/satisfiability/doc .
[6] Flener, P., Pearson, J., & Ågren, M. (2003). Introducing ESRA, a relational language for modelling combinatorial problems. In LOPSTR, International Symposium on Logic-based Program Synthesis and Transformation, (pp. 214–232). · Zbl 1099.68543
[7] Fourer, R., Gay, D. M., & Kernighan, B. W. (2002). AMPL: A modeling language for mathematical programming. Pacific Grove: Duxbury Press. · Zbl 0701.90062
[8] Frisch, A., Grum, M., Jefferson, C., Martinez Hernandez, B., & Miguel, I. (2007). The design of ESSENCE: A constraint language for specifying combinatorial problems. In Proc. of the 20th international joint conference on artificial intelligence IJCAI.
[9] Frisch, A. M., Jefferson, C., Martinez-Hernandez, B., & Miguel, I. (2005). The rules of constraint modelling. In Proc 19th IJCAI, (pp. 109–116).
[10] Frisch, A. M., Harvey, W., Jefferson, C., Martìnez-Hernàndez, B., & Miguel, I. (2008). Essence: A constraint language for specifying combinatorial problems. Constraints (this issue). · Zbl 1147.68424
[11] Gervet, C. (2001). Large scale combinatorial optimization: A methodological viewpoint. DIMACS Discrete Mathematics and Theoretical Computer Science, 57, 151–174. · Zbl 0983.90040
[12] Hakin, A. (1985). The intractability of resolution. Theoretical Computer Science, 39, 297–308. · Zbl 0586.03010 · doi:10.1016/0304-3975(85)90144-6
[13] Hnich, B., Miguel, I., Gent, I. P., & Walsh, T. CSPLib: a problem library for constraints. http://www.csplib.org/ .
[14] Jayaraman, B., & Tambay, P. (2002). Modeling engineering structures with constrained objects. In PADL, (pp. 28–46). · Zbl 1049.68689
[15] Kallrath, J. (2004). Modeling languages in mathematical optimisation. Norwell: Kluwer. · Zbl 1049.90002
[16] Lauriere, J-L. (1978). ALICE: A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10(1), 29–127. · Zbl 0374.68060 · doi:10.1016/0004-3702(78)90029-2
[17] Marriott, K., Stuckey, P. J., & Wallace, M. (2006). Constraint logic programming. In Handbook of constraint programming (pp. 409–452). Amsterdam: Elsevier.
[18] Murtagh, B. A. (1981). Advanced linear programming (pp. 163–170). Columbus: McGraw-Hill.
[19] Rafeh, R., Garcia de la Banda, M. J., Marriott, K., & Wallace, M. (2007). From Zinc to design model. In Proc. PADL 2007 Number 4354 in LNCS (pp. 215–229). New York: Springer. · Zbl 1146.68352
[20] Schneider, S. (2001). The B-method: An introduction. Cornerstones of Computing. Hampshire: Palgrave.
[21] Solvers that work with AMPL. http://www.ampl.com/solvers.html .
[22] Somogyi, Z., Henderson, F., & Conway, T. (1996). The execution algorithm of Mercury: an efficient purely declarative logic programming language. Journal of Logic Programming, 29(1–3), 17–64. · Zbl 0877.68015 · doi:10.1016/S0743-1066(96)00068-4
[23] Stefik, M. (1981). Planning with constraints (MOLGEN: Part 1). Artificial Intelligence, 16, 111–139. · doi:10.1016/0004-3702(81)90007-2
[24] Stuckey, P. J., García de la Banda, M. J., Maher, M. J., Marriott, K., Slaney, J. K., Somogyi, Z., et al. (2005). The G12 project: Mapping solver independent models to efficient solutions. In CP, (pp. 13–16). · Zbl 1165.68517
[25] Van Hentenryck, P., Lustig, I., Michel, L. A., & Puget, J.-F. (1999). The OPL optimization programming language. Cambridge: MIT Press.
[26] Van Hentenryck, P. & Michel, L. (2005). Constraint-based local search. Cambridge: MIT Press. · Zbl 1153.90582
[27] Wallace, M., Novello, S., & Schimpf, J. (1997). ECLiPSe–a platform for constraint programming. ICL Systems Journal, 12(1), 159–200.
[28] Weisstein, E. W. (1999). Perfect square dissection. From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/PerfectSquareDissection.html .
[29] Yeomans, J. (2003). Solving Einstein’s riddle using spreadsheet optimisation. INFORMS Transactions on Education, 3(2).
[30] Yuen B. J., & Richardson K. V. (1995). Establishing the optimality of sequencing heuristics for cutting stock problems. European Journal of Operational Research, 84, 590–598. · Zbl 0918.90125 · doi:10.1016/0377-2217(95)00025-L
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.