2.5 MiniZinc

MiniZinc is an open-source, solver-independent constraint modeling language. The MiniZinc Software includes also the solvers Gecode, Chuffed, COIN-OR CBC, and a Gurobi interface (see [8]). One can also model linear or non-linear optimization problems. Like other algebraic modeling languages, MiniZinc contains sets (defined as arrays), parameter, variables, constraints and solve instructions to formulate a model in a purely declarative way. As a language for constraint programming, constraints can contain Boolean operators, such as and (/' ), or (' /), imply (->), or not equal (!=) operators, etc. One of the most interesting and prominent feature of MiniZinc (and of other constraint programming systems) is its library of global constraints (see for example Global Constraint Catalog). Without going into the details here, two examples are given: (1) The alldifferent function constrains a set of (integer) variables to be all different from each other. (2) The at_most function requires at most n variables in a set of variables to take the given value v. Some of these global constraints could be expressed in a common mathematical notation, but – depending on the solver used – this would be inefficient. Given a set of integer variables xi with i,j I, the alldifferent constraint, for example, could be expressed as

xi ⁄= xj   forall i,j ∈ I, j > i

The atmost constraint could be expressed as:

    (x =  v) = n

Expressing these constraints using a function name has the advantage that the constraint programming system recognizes them and can apply special and more efficient algorithms. MiniZinc contains many global constraints (see the Reference Manual of MiniZinc and it is the real strength of this language.

Two models are given to show Boolean modeling and the use of alldifferent constraint in MiniZinc.

   2.5.1 Sudoku Puzzle (sudokuM)
   2.5.2 Light Up Puzzle (lightup1)