×

zbMATH — the first resource for mathematics

MiniZinc with functions. (English) Zbl 1382.68234
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 268-283 (2013).
Summary: Functional relations are ubiquitous in combinatorial problems – the global constraint catalog lists 120 functional constraints. This paper argues that the ability to express functional constraints with functional syntax leads to more elegant and readable models, and that it enables a better translation of the models to different underlying solving technologies such as CP, MIP, or SAT.
Yet, most modelling languages only support built-in functions, such as arithmetic, Boolean, or array access operations. Custom, user-defined functions are either not catered for at all, or they have an ad-hoc implementation without a useful semantics in Boolean contexts and not exploiting potential optimisations.
This paper develops a translation from MiniZinc with user-defined functions to FlatZinc. The translation respects the relational semantics of MiniZinc, correctly dealing with partial functions in arbitrary Boolean contexts. At the same time, it takes advantage of the full potential of common subexpression elimination.
For the entire collection see [Zbl 1263.68017].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI