Monash University

Design of the MiniZinc language, lazy clause generation solvers, modelling interesting problems, developing and teaching Basic Modeling for Discrete Optimization (and other MOOCs).

Conditionals are a core concept in all programming languages.
They are also a natural and powerful mechanism for expressing complex
constraints in constraint modelling languages.
The behaviour of conditionals is complicated by undefinedness.
In this paper we show how to most effectively translate conditional constraints
for underlying solvers. We show that the simple translation into implications can be improved,
at least in terms of reasoning strength, for both constraint programming
and mixed integer programming solvers. Unit testing shows that
the new translations are more efficient, but the benefits are
not so clear on full models
where the interaction with other features such as learning is more
complicated.

MiniZinc is a solver agnostic modeling language for defining and solver
combinatorial satisfaction and optimization problems. MiniZinc provides a
solver independent modeling language which is now supported by constraint
programming solvers, mixed integer programming solvers, SAT and SAT modulo
theory solvers, and hybrid solvers. Since 2008 we have run the MiniZinc
challenge every year, which compares and contrasts the different strengths
of different solvers and solving technologies on a set of MiniZinc models.
Here we report on what we have learnt from running the competition for 6
years.

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.

Copyright © Monash University and Data61, CSIRO, 2014, 2015, 2016, 2017, 2018, 2019