Gecode: Publications

MiniZinc: Towards a Standard CP Modelling Language

Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, Guido Tack.

There is no standard modelling language for constraint programming (CP) problems. Most solvers have their own modelling language. This makes it difficult for modellers to experiment with different solvers for a problem.

In this paper we present MiniZinc, a simple but expressive CP modelling language which is suitable for modelling problems for a range of solvers and provides a reasonable compromise between many design possibilities. Equally importantly, we also propose a low-level solver-input language called FlatZinc, and a straightforward translation from MiniZinc to FlatZinc that preserves all solver-supported global constraints.

This lets a solver writer support MiniZinc with a minimum of effort - they only need to provide a simple FlatZinc front-end to their solver, and then combine it with an existing MiniZinc-to-FlatZinc translator. Such a front-end may then serve as a stepping stone towards a full MiniZinc implementation that is more tailored to the particular solver.

A standard language for modelling CP problems will encourage experimentation with and comparisons between different solvers. Although MiniZinc is not perfect - no standard modelling language will be - we believe its simplicity, expressiveness, and ease of implementation make it a practical choice for a standard language.

In: Christian Bessière, editor, Thirteenth International Conference on Principles and Practice of Constraint Programming, Providence, RI, USA, volume 4741 of Lecture Notes in Computer Science, pages 529-543. Springer-Verlag, September, 2007.

Copyright Springer-Verlag, the original publication is available at www.springerlink.com