ATHANOR

Automated, scalable, local search of constraint satisfaction and constraint optimisation problems written in Essence

• IJCAI paper here
• Why use ATHANOR
• Using ATHANOR
• Building from source
• Demo the web app version! ATHANOR can now run efficiently inside your web browser, thanks to web assembly.

Why use ATHANOR

Powerful specifications:

ATHANOR is a local search solver for constraint problems expressed in the Essence language. Essence allows for the specification of constraint problems using high level mathematical types -- such as set, sequence and partition -- which are not available in other constraint modelling languages. These high level types can be arbitrarily nested -- for example, set of partition, set of sequence of tuple of ..., etc. The high level nature of Essence allows for very concise specifications of constraint problems as the user is not required to make many modelling decisions. For example, how a set of sequence of tuple (int, int) should be represented.

Performance:

The information conveyed by the high level Essence types allow for a more performant and more scalable local search. These benefits are described in a paper published in the 2019 proceedings of the International Joint Conference for Artificial Intelligence. In this paper, we benchmark ATHANOR against six state of the art local search constraint solvers.

In short:

• Performance: ATHANOR uses the high level Essence types to derive more semantically meaningful neighbourhoods for its local search.
• Scalability: ATHANOR understands that structures such as sets, multi-sets and sequences can have a variable cardinality during search. Hence, unlike traditional solvers, which must pre allocate memory to support every structure reaching its maximum size, ATHANOR dynamically allocates and de-allocates memory during search according to the cardinality of the structures.

Multiple solvers:

Conjure is a great automated constraint modelling tool that accepts Essence as an input language. It is part of a toolchain that can automatically refine high level Essence specifications into an input suitable for a range of solvers including CP, SAT, and more. Find out more here.

Using ATHANOR

Essence

• Typically, Essence problems are divided into a specification file and a parameter file. An Essence specification describes the problem class -- given some input X, the desired output should be Y. The parameter file is then used to specify a particular instance of X.
• An Essence specification normally consists of
  1. Givens: descriptions of the input domains,
  2. Finds: declaration of decision variables, variables used to encode solutions to the problem.
  3. Constraints: constraints that the values assigned to the decision variables must satisfy.
  4. Objective: an expression to minimise or maximise. This may be an integer or a tuple of integers which is lex ordered.
• The parameter file is just a set of constants specified using lettings.
• Getting started, some example essence problems that work with ATHANOR [coming soon].
• Read Essence documentation here. ATHANOR operates on a subset of Essence. Feature requests are very welcome! Supported types: int, bool, enum, tuple, set, multi-set, sequence, function (total) int --> *, function (total) tuple(int,int, ...) --> *, partition (regular, fixed number parts), record.

Obtaining ATHANOR

• Obtain the latest ATHANOR Mac or Linux releases here.
• Manual installation instructions here.
• Or try out the ATHANOR web app, it runs natively and efficiently in your browser, thanks to Web Assembly.
• ATHANOR depends on Conjure to parse Essence. A Conjure executable is bundled with the releases and ATHANOR should be able to appropriately locate it.

Basic usage:

• ./athanor --spec path_to_essence_spec [--param path_to_essence_param]
• Essence specifications are usually split into two parts, the specification of the problem and the parameters to the problem.
• ATHANOR invokes Conjure to translate the given files into a JSON representation.
  • If you wish to skip this step when invoking ATHANOR, the translation can be manually invoked through Conjure before running ATHANOR. a bash script manualBuildAthanorInput.sh has been included to help.

Building from source:

The latest versions of ATHANOR can be installed manually.

Requirements:

• GNU Make
• cmake 3.0 onwards.
• C++14 compatible compiler.
  • clang: According to clang's documentation, c++14 is supported with versions of clang 3.4 and later. However, ATHANOR has only been tested on clang 5 onwards.
  • gcc: Unfortunately, due to internal compiler bugs, only the newest gcc compilers are compatible with ATHANOR. Use gcc 8 onwards.
• Conjure, (for running ATHANOR after installation). Conjure must either be in the path or be located next to the ATHANOR executable.

Installation:

Quick install:

git clone https://github.com/__ATHANOR__/__ATHANOR__
cd __ATHANOR__
make

For parallel build, make -jn replacing n with number of cores.

Note, you can specify the compiler to use by writing export CXX=PUT_COMPILER_COMMAND_HERE. For example export CXX=clang++.

The binary athanor will be placed in <pwd>/build/release/athanor

Manual install:

git clone https://github.com/__ATHANOR__/__ATHANOR__
cd __ATHANOR__

Now additional libraries need to be pulled from github.

git submodule init
git submodule update

Then make a build directory and build ATHANOR there

mkdir -p build/release
cd build/release
cmake ../..
make

For parallel build, make -jn replacing n with number of cores.

Note, you can specify the compiler to use by writing export CXX=PUT_COMPILER_COMMAND_HERE. For example export CXX=clang++.

Who am I