Documentation

Overview

  1. Getting Started: Using the Graphical User Interface
  2. Running Solvers from Tailor
  3. Input Formats
  4. Target Solvers

1. Getting Started: The Graphical User Interface

The graphical user interface(GUI) can be used to model problems, tailor them to solver format, and also to solve problems directly by calling a solver externally.

The GUI is started by either double-clicking the file 'tailor.jar' or executing the command 'java -jar tailor.jar' in the command line. The image below shows Tailor's GUI of version 0.3.2. It is devided into an input part (left) and an output part (right). The drop-down menus and buttons in the middle enable you to select your target solver and select between solving and tailoring.



The input part to the left has two fields for modelling: the top field is used to model the problem; the bottom field to specify parameter values (data). The parameter field can be left empty. There is a series of Essence' examples in the /examples directory of your Tailor distribution (like the Golomb Ruler model in the image) to get familiar with modelling in Essence'.

The output part on the right summarises the results from Tailor: the top right field is a collection of tabs, each showing the translation output at a different stage: normalised Essence', flattened Essence', solver input and the Essence' solution. The content of each tab can be saved using the 'Save Tab' button.

In between the input and output part, there are drop-down menus to select a translation mode: solve or tailor.
If solve is selected, Tailor will translate your problem into the corresponding solver format, save it in a file, execute the solver on the file (in a separate process), and return the solver output on the right side. More information about how to set up the solver for Tailor is given below.
If tailor is selected, Tailor will translate your problem into the selected output format (Minion input, Gecode input(C++), FlatZinc or flat Essence') and show it on the right hand top text field.

The text field on the bottom right shows system and error messages.

There are several different translation options that can be selected in the 'Translation' menu on the top left side of the window. Interesting options are:
  • Giving information about auxiliary variables: this option will display the expression that an auxiliary variable represents when the variable is defined (the information is given in a comment). This can be very helpful when altering (or trying to understand) the solver input.
  • Common Subexpression Elimination: is an enhancement technique which can further enhance your constraint instance but may increase tailoring time when performed extensively. Here you can decide upon the extent of common subexpression elimination. Note that the default settings typically don't increase tailoring time.


2.Running Solvers from Tailor

Tailor's GUI allows users to execute solvers in a separate process without having to deal with the solver input language. Below we first describe how to set up Tailor to run Minion and Gecode. Then we discuss what solving settings are used when calling the solvers.
Note that all solvers/tools are open source software and that Tailor is mainly tested on Linux and Macs.

Using Minion in Tailor

In order to execute Minion from Tailor, you need to first install a Minion executable on your machine, which you can get from Minion's download page. Then you will need to specify the path to your Minion executable: click on 'Settings' in the GUI top menu and chose 'Set path to Minion'. Done!

Using Gecode in Tailor

Tailor runs Gecode through the Flatzinc/Gecode interpreter. Therefore, in order to solve problems in Gecode from Tailor you need two things: first, you will need to install the Gecode library - there is an extensive documentation how to do this on Gecode's docu page. Second, you will need Flatzinc/Gecode which interprets Flatzinc files with Gecode. Make sure that FlatZinc/Gecode is properly set up for Gecode (see its homepage for more details). Tailor will call the Flatzinc/Gecode executable 'fz' in its working directory, so either add 'fz' to your PATH or copy 'fz' into to the same directory as Tailor. You can set the PATH on Linux and Macs by modifying your .bash.rc or .profile file in your home-directory or by the command 
       bash> export PATH=$PATH:/path/to/fz
for bash shells. Done!

Default Solving Settings

By default, Tailor will ask for one solution from the solver (except for optimisation problems), but this can be changed in the top menu of the GUI in 'Solving'. Tailor will print solving statistics with the solution (typically in a comment) and will show the exact solving command in the System Messages field.

Note that Tailor does not put any effort into chosing search heuristics. Variables are ordered according to their order in the Essence'/XCSP problem model. Auxiliary variables are not branched on (by default). Values are ordered using the default method (ascending in Minion). If you (are an expert and) wish to adapt the search heuristics to your problem, then chose 'tailor' instead of 'solve' in the GUI and modify the generated solver input.

3. Tailoring Essence'

Essence' is a solver-independent modelling language, which is extensively documented in this pdf file. An introduction into modelling with Essence' is given here. We also provide tools for syntax highlighting of Essence'.

4. Tailoring XCSP FORMAT

Tailor supports XCSP Format 2.1 which is the input format of the XCSP solver competitions. There is a large set of benchmarks, including a wide range of problem families. Note that Tailor's graphical interface is restricted to Essence' input only, so XCSP instances can only be translated with the command line version. As an example, the following command (in a shell) would translate the xml file `queens-10.xml' to Minion: 
shell> java -jar tailor.jar -xcsp queens-10.xml
XCSP files can be very big, so Tailor also supports .bz2 files as input. As an example, the following command would translate the compressed file `queens-10.xml.bz2' to Gecode. 
shell> java -jar tailor.jar -g -xcsp queens-10.xml.bz2
Note, that on some XCSP instances TAILOR runs out of memory. This can be averted by increasing the memory of the Java virtual machine by the extended command 
shell> java -Xms128m -Xmx512m -jar tailor.jar -xcsp queens-50.xml
where the flag `-Xms128m' sets the initial size, `-Xmx512m' sets the maximum size of the memory allocation pool to 128MB/512MB. This setting should be sufficient to tailor large instances.

5. Tailoring to Minion

Tailor supports solver Minion, a fast constraint solver that takes a simple text file as input. Minion is a black-box solver, hence it is difficult to extend or alter, but easy to use. Minion takes problem instances as input, and does not supported parameterised problems, i.e. problem classes. Hence all parameter values need to be specified in order to produce a valid Minion input file.

Tailor can generate Minion files in the command line version and the graphical user interface(GUI). The command line version is practical when tailoring many problem files (for instances for testing), while the GUI is practical for modelling or testing a model's performance. The graphical user interface is evoked by either double-clicking the file `tailor.jar' or typing the following into the command line: 

shell> java -jar tailor.jar
Here is an example for the command line, where a problem model in the file `myProblem.eprime' is tailored to Minion: 
shell> java -jar tailor.jar myProblem.eprime
This will generate the file myProblem.eprime.minion. You can specify the output file name with the command: 
shell> java -jar tailor.jar -out myProblem.minion myProblem.eprime
which will write the Minion input into the file `myProblem.minion'.


Tailor's graphical user interface allows to solve constraint models using Minion in 4 simple steps:
  1. Model the problem in Essence' and specify parameter values
  2. Translate the problem to Minion input format
  3. Run Minion (after specifying the path to the Minion executable)
  4. If Minion finds a solution, the values are mapped into Essence' format
Support/Limitations::
  • maximum of 3-dimensional arrays (4- or more-dimensional arrays not supported)
  • Supported global constraints: alldifferent, element atmost, atleast, table

6. Tailoring to Gecode

Tailor can translate Essence' and XCSP format to solver Gecode, a powerful constraint toolkit. Please note that the translation is still restricted (for limitations see below). Gecode is a white-box solver, i.e. it is a C++ library that allows the user to easily alter and customise the library, which makes modelling more difficult. Note that the input language of Gecode (i.e. C++) is far more expressive than Essence'/XCSP. Therefore, Tailor is restricted to use the standard tools provided by Gecode, which a Gecode expert would probably customise to the given problem. Performing such `expert' alterations automatically is currently out of scope of automated modelling. This means that Tailor cannot replace a Gecode expert but give assistance, especially to novices with Gecode.

Note that Tailor can tailor problem classes to Gecode, since problems are represented by C++ classes, where parameters can be specified at runtime. In general, it is better to tailor the whole class, instead of tailoring every instance since it saves tailoring time, and problem classes can be expressed more compactly than problem instances in C++.

Getting started
Tailor converts Essence'/XCSP to Gecode in both the command line version and the graphical user interface. The command line version is practical when tailoring many problem files (for instances for testing), while the GUI is practical for modelling or testing a model's performance. The graphical user interface is evoked by either double-clicking the file `tailor.jar' or typing the following into the command line: 

shell> java -jar tailor.jar
Here is an example for the command line, where a problem model in the file `myProblem.eprime' is tailored to Gecode: 
shell> java -jar tailor.jar -g myProblem.eprime
This will generate the file myProblem.eprime.cc. You can specify the output file name with the command: 
shell> java -jar tailor.jar -g -out myProblem.cpp myProblem.eprime
which will write the C++ class into the file `myProblem.cpp'. To get started, have a look at our set of Essence' examples; an easy example would be the Langford Number Problem.

Compiling generated Gecode files
Tailor produces C++ files that need to be compiled in order to be executed. All generated C++ files inherit the `Example' class. One way of compiling a problem file is by using the existing `make' file:

  1. Copy your C++ file, e.g. myProblem.cc, into Gecode's example directory (top-level of your Gecode version). For instance, with Gecode version 3.0.1: 
     shell> cp myProblem.cc gecode-3.0.1/examples
  2. Edit the make-file `Makefile' in Gecode's toplevel: add the name of your file to the examples list at the example part of the Makefile: 
    #
# EXAMPLES
#

INTEXAMPLESRC0 =						\
	alpha bacp bibd donald myProblem \
        eq20 golomb-ruler tsp \
        ....
    Only put the file name WITHOUT the extension! Then save the Makefile.
  3. Execute make by typing `make' into the command line at Gecode's top level. This compiles all the example files in the /examples directory that are listed in the Makefile if they have been changed. You will find your executable in Gecode's example directory, e.g. gecode-3.0.1/examples/myProblem
  4. Run your problem, for example on Linux in a shell by: 
     shell> ./gecode-3.0.1/examples/myProblem
Alternative (and probably simpler) ways to compile your C++ file can be found at Gecode's website.

Gecode Features used in the Translation
Tailoring to Gecode was highly inspired by the examples provided by the Gecode developers. In the following, we give a brief overview of which standard tools in Gecode are used in the tailoring process. Note that this information is probably only interesting to people who have some experience with Gecode.

  • Variable types: Tailor uses the following types: IntVars, BoolVars, IntVarArrays and BoolVarArrays and the corresponding argument variables if possible. No set variables are used. 2-dimensional arrays are flattened to 1-dimensional arrays which are accessed using a method.
  • Arithmetic Constraints: whenever possible, Tailor tries to use the `linear' propagator and flattens expressions if necessary. `post' is not used. Arguments that are shared amongst different linear propagators are reused.
  • Relational Constraints: are represented by the `rel' propagator, if possible. `post' is not used.
  • Parameters: are defined by specifying a customised Option class, in which Tailor generates (more or less) random default values for each parameter and provides a help message that describes the parameters and gives the default values.
  • Heuristics: Tailor does not put any effort into determining an appropriate search and labelling heuristic, and hence uses the same heuristic for every problem: smallest value first. The decision variables are branched in the order they were defined in the Essence'/XCSP file. Search is not applied on auxiliary variables. By default, only 1 solution is searched.
  • Other: Tailor provides a print method that prints all decision variables that are printed in the order of their definition. The header of the C++ file contains statistics about the number of propagators and auxiliary variables.

Limitations
The translation to Gecode is still under construction, so we there are certain limitations, which we summarise below.

  • only 1- and 2-dimensional arrays are supported (3- or more-dimensional arrays not supported)
  • no support for parameter arrays or constant arrays
  • no support for existential quantification
  • Supported global constraints: alldifferent, element
  • Lex Constraint not supported yet