| Constraints programming is usually done in two steps: | 1) Creation of an conceptual model, an abstraction of some real-world problem.
2) Design of a program that solves the problem |
| MiniZinc | MiniZinc is a modeling language being developed mostly by
NICTA (Australia)
MiniZinc ⊂ Zinc – a more powerful modeling language |
| Running MiniZinc | MiniZinc models must have mzn extension and data dzn |
| A MiniZinc model consists of a sequence of items | An inclusion item include <filename (string)>;
An output item output <list of string expressions>;
Declaration of a variable
A constraint constraint <Boolean expression>;
A solve item (only one of the following is allowed)
- solve satisfy;
- solve maximize <arith. expression>;
- solve minimize <arith. expression>;
predicates and asserts (for checking parameter values)
Search annotation items ann |
| Writing Efficient Models I | Add search annotations to the solve item to control exploration of the search space
first_fail (MRV): choose the variable with the smallest domain size
indomain_min: assign the variable its smallest domain value
See reference manual for a complete list of heuristics |
| Writing Efficient Models II | Use global constraints such as alldifferent since they have better propagation behavior
Try different models for the problem
Add redundant constraints
Bound variables as tightly as possible (avoid var int)
Avoid introducing unnecessary variables |
| Summary | MiniZinc is a language designed for specification of decision and optimisation problems
The model is declarative, although it can contain annotations
The language provides large number of operators and built-in functions to simplify modelling
Advanced models in MiniZinc use predicates to define complex subproblem constraints
Global constraints (better solving)
User defined constraints (better readability)
Efficiency depends on the model formulation
Developing an efficient decision model requires sometimes considerable experimentation
(NP-hard problems are hard problems) |
