MiniZinc: Towards a Standard CP Modelling Language

MiniZinc: Towards a Standard CP Modelling Language

2007 | Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack
MiniZinc is a standard constraint programming (CP) modelling language designed to enable modellers to experiment with different solvers for a problem. It provides a reasonable compromise between design flexibility and simplicity, and is suitable for a range of solvers. Alongside MiniZinc, a low-level solver-input language called FlatZinc is proposed, with a straightforward translation from MiniZinc to FlatZinc that preserves all solver-supported global constraints. This allows solver writers to support MiniZinc with minimal effort by providing a simple FlatZinc front-end to their solver, combined with an existing MiniZinc-to-FlatZinc translator. This approach serves as a stepping stone towards a full MiniZinc implementation tailored to a particular solver. A standard CP modelling language would encourage experimentation with and comparisons between different solvers. Although MiniZinc is not perfect, its simplicity, expressiveness, and ease of implementation make it a practical choice for a standard language. The main challenges in proposing such a language are finding a reasonable middle ground between different solvers' capabilities and encouraging people to use the language. This paper makes two contributions that address these challenges: (1) a CP modelling language suitable as a standard, and (2) a simple way to implement MiniZinc. MiniZinc is a medium-level declarative language that is high-level enough to express most CP problems easily and in a solver-independent way. It supports sets, arrays, user-defined predicates, and some overloading. It is low-level enough to be mapped easily onto many solvers, supporting only decision variable types that are supported by most existing CP solvers. MiniZinc allows separation of a model from its data, provides a library of global constraints, and has a system of annotations for non-declarative information. FlatZinc is a low-level solver input language that is the target language for MiniZinc. It is designed to be easy to translate into the form required by a CP solver. A standard translation from MiniZinc to FlatZinc is defined, involving well-understood transformations such as predicate inlining and reification. This translation allows solvers to use native definitions of any global constraints they support, while decomposing unsupported ones into lower-level constraints. This provides an excellent starting point for an implementation. The paper concludes with a discussion of future work and related research.MiniZinc is a standard constraint programming (CP) modelling language designed to enable modellers to experiment with different solvers for a problem. It provides a reasonable compromise between design flexibility and simplicity, and is suitable for a range of solvers. Alongside MiniZinc, a low-level solver-input language called FlatZinc is proposed, with a straightforward translation from MiniZinc to FlatZinc that preserves all solver-supported global constraints. This allows solver writers to support MiniZinc with minimal effort by providing a simple FlatZinc front-end to their solver, combined with an existing MiniZinc-to-FlatZinc translator. This approach serves as a stepping stone towards a full MiniZinc implementation tailored to a particular solver. A standard CP modelling language would encourage experimentation with and comparisons between different solvers. Although MiniZinc is not perfect, its simplicity, expressiveness, and ease of implementation make it a practical choice for a standard language. The main challenges in proposing such a language are finding a reasonable middle ground between different solvers' capabilities and encouraging people to use the language. This paper makes two contributions that address these challenges: (1) a CP modelling language suitable as a standard, and (2) a simple way to implement MiniZinc. MiniZinc is a medium-level declarative language that is high-level enough to express most CP problems easily and in a solver-independent way. It supports sets, arrays, user-defined predicates, and some overloading. It is low-level enough to be mapped easily onto many solvers, supporting only decision variable types that are supported by most existing CP solvers. MiniZinc allows separation of a model from its data, provides a library of global constraints, and has a system of annotations for non-declarative information. FlatZinc is a low-level solver input language that is the target language for MiniZinc. It is designed to be easy to translate into the form required by a CP solver. A standard translation from MiniZinc to FlatZinc is defined, involving well-understood transformations such as predicate inlining and reification. This translation allows solvers to use native definitions of any global constraints they support, while decomposing unsupported ones into lower-level constraints. This provides an excellent starting point for an implementation. The paper concludes with a discussion of future work and related research.
Reach us at info@study.space