« Common constraint programming problems | Main | G12 MiniZinc version 1.0.2 released »

New Tailor version (v0.3.2) and My Essence'/Tailor page

Since I have not written much about Tailor before, here is a short presentation of the system:
TAILOR is a tool that facilitates modelling and solving constraint models. TAILOR's graphical user interface (GUI) allows the user to directly solve an Essence' problem model with either solver MINION or GECODE, and is hence especially aimed at people who are novices in constraint programming or have no experience with constraint solvers Minion and Gecode. Note that TAILOR is not intended to compare solvers, but to generate effective solver input from a solver-independent problem model.
...

TAILOR provides a command-line and an interactive graphical version. TAILOR is distributed as a Java .jar file and can easily be executed on every platform.
Tailor is developed by Andrea Rendl of University of St Andrews in Scotland, UK.

New version v0.3.2

A new Tailor version was released some days ago. From the NEWS:
July 15, 2009: NEW RELEASE : TAILOR v0.3.2 (bug-fixed update from July 19, 2009) New Features * New output format: Flatzinc (still limited though) * New GUI options: o Solve your model directly in TAILOR with solver Gecode by using the Gecode-Flatzinc interpreter * Extended Gecode Translation (still restricted though) * several bugfixes (especially with XCSP format)
The Flatzinc output format is especially interesting, since there are now a lot of different solvers for solving Essence' models. A later finding reveals that there may have to be some tweakings in the FlatZinc file for using it with other solvers than Gecode/FlatZinc, since the translation (tailoring) is done explicitly for Gecode/FlatZinc.

Also, right now Tailor cannot generate FlatZinc files when the Essence' model contains multi dimensional arrays (matrices), but - as I understand it - this may come quite soon.

One should note that in Essence' it is not possible to stating search heuristics options. But it's quite easy to manually change that for the generated FlatZinc models (or, as I probably will do: make a program doing that). For the Minion solver there is a -varorder switch that change the variables order, but "[t]his flag is experimental and minion's default ordering might be faster" (to quote the help for the switch).

This can be examplified by the Calculs d'enfer puzzle, a minimizing alphametic puzzle. This is very slow for both Gecode/FlatZinc and Minion using the default solver settings. These remedies makes it much faster:
* FlatZinc: change (in the FlatZinc file) the solver clause to solve :: int_search(A, first_fail, indomain, complete) minimize a_max;
* Minion: Run Minion as minion -varorder srf calculs_d_enfer.eprime.minion

Update: In my simple wrapper program eprime.pl (Perl program) which I tend to use, I have now added support for "annotations" in the Eseence' file which handle these things The model now contains these two lines::
$ MINION :: -varorder srf
$ FLATZINC:: solve :: int_search(A, first_fail, indomain_min, complete) minimize a_max;
The MINION annotation simply adds -varorder srf to the argument list of the minion program, and the FLATZINC annotation replaces the default line solve satisfy, with the int_search parameter.
Note: The program eprime.pl is not very tidy but may be obtainable upon request. (end of update)

Some notes about the Essence' language

The language used in Tailor is Essence' (it also supports XCSP files ). This is a simplified version of ESSENCE (no prime). For more about Essence' see Modelling with Essence' and the examples. Also, see the Tailor tutorial.

Essence' is similiar to MiniZinc in its high-level approach, and it was very easy to translate (most of) the MiniZinc models to Essence'.

Example: Minesweeper

As an example, here is the complete model of Minesweeper (the param lines are usually in a separate parameter file): 
ESSENCE' 1.0
letting X be -1 $ the unknowns
letting AB be domain int(-1..1)
given r : int $ rows
given c : int $ column
$ encoding: -1 for unknown, >= 0 for number of mines in the neighbourhood
given game : matrix indexed by [int(1..r),int(1..c)] of int(-1..8)

find mines : matrix indexed by [int(1..r),int(1..c)] of int(0..1)

$ Problem from Gecode/examples/minesweeper.cc  problem 0
param r be 6
param c be 6
param game be [
   [-1,-1,2,-1,3,-1],
   [2,-1,-1,-1,-1,-1],
   [-1,-1,2,4,-1,3],
   [1,-1,3,4,-1,-1],
   [-1,-1,-1,-1,-1,3],
   [-1,3,-1,3,-1,-1]
   ]

forall i : int(1..r) . forall j : int(1..c) . 
  (     
   ((game[i,j] > -1) => (mines[i,j] = 0)) /\
   ((mines[i,j] = 1) => (game[i,j] = -1)) /\
   (
    (game[i,j] >= 0 ) =>
      (
       game[i,j] = sum a,b : AB .
          ( (i+a > 0)  /\ (j+b > 0) /\
            (i+a <= r) /\ (j+b <= c)) * (mines[i+a,j+b])
      )
    )
  )
Compared to the MiniZinc model minesweeper.mzn, we can see some things:
* The where clause is missing in Essence'. Instead a condition is used, here: (game[i,j] >= 0 ) =>.
* Also, the syntax of the forall statement is somewhat different.
Otherwise it's quite similiar.

One feature I like it the "array slice" operator (e.g. x[i,..]) which slices all the columns of row i. For example, in quasigroup_completion.eprime the following to constraints makes a matrix a lating square: 
forall i : int(1..n) .
   alldiff(x[i,..]),

forall j : int(1..n) .
   alldiff(x[..,j])
One of the biggest differences between Essence' and MiniZinc languages (and all the other constraint programming systems I've tested so far) is, in my view, that Essence' don't support predicates (user defined functions), which can make the model less clear; predicates (say, decomposed global constraints) is a nice way of structuring models.

Array access in Essence'

One of the things I test when learning a new system is how to access matrices consisting of decision variable indexed by another decision variables. I wrote about this in Learning constraint programming - part II: Modeling with the Element constraint and Learning Constraint Programming IV: Logical constraints: Who killed Agatha? revisited.

There was no problem at all in Essence' of modeling the Agatha problem: The model is here who_killed_agatha.eprime. The following two constraints, which has been a problem in some other systems, worked as a charm in the Essence' model: 
hates[the_killer, the_victim] = 1,
richer[the_killer, the_victim] = 0,
The crossword problem, however, is another story. I used exactly the same principle as in the MiniZinc model crossword.mzn, but the Essence' constraint 
A[E1, 3] = A[E2, 1]
give the following error: Flattening error. Cannot translate array element with non-constant element index:A[E3,5].

Well, this is consistent with the section 6. Limitations and Known Bugs in the README file of the distribution: 
The translator is still under development, so there are some limitations. 
The following is not supported yet:
- decision variable arrays with 4 or more dimensions
- parameter arrays with 4 or more dimensions
- absolute value
- power with decision variable as exponent
- element constraint on 2-dimensional arrays

Translation to Gecode:
- no parameter arrays supported
- complicated quantified sums not supported

Translation to Flatzinc:
- not supported: multi-dimensional arrays
- no support for table, element, atmost, atleast, gcc
- no modulo, power, division

My Essence'/Tailor page

Inspired by this new Tailor release, I implemented some Essence' models which now are collected at My Essence'/Tailor page. As usual, I started with my "learning models", and implemented almost all of them.

Here are the Essence' models (and related parameter/data files) as of writing: I have also updated Common constraint programming problems to include these Essence' models.

Posted by hakank on July 25, 2009 09:51 AM |