Second International CSP Solver Competition

(

Held in conjunction with

Twelfth International Conference on Principles and

Practice of Constraint Programming (CP'06)

Nantes, France

Marc van Dongen |

Christophe Lecoutre |

Olivier Roussel |

Radoslaw Szymanek |

Fred Hemery |

Chris Jefferson |

Rick Wallace |

The Second International CSP Solver Competition is organised
to improve our understanding of the sources of solver efficiency, and
the options that should be considered in crafting solvers.
In particular, issues of interdependence
and interaction among features can perhaps only be elucidated by comparing
and testing actual implementations.
It is hoped that efforts like this will further our
understanding of the important dimensions of performance, for example
robustness or versatility as opposed to problem-specific efficiency.

- 1 Introduction
- 2 Scope
- 3 Rules and Regulations
- 4 Format Specification

- 5 Ranking
- 6 Evaluation
- 7 Preprocessing
- 8 Solver Script

- 9 Diagnostics
- 10 Categories

- 11 Benchmarks
- 12 Submission Process
- 12.1 Solver Submission Process
- 12.2 Conversion Script Certification Process
- 12.3 Problem Submission Process

- 13 Important Dates for the Competition
- 14 Organising Committee
- 15 Links
- 16 Sponsors

The Second International CSP Solver Competition is organised to improve our understanding of the sources of solver efficiency, and the options that should be considered in crafting solvers. In particular, issues of interdependence and interaction among features can perhaps only be elucidated by comparing and testing actual implementations. It is hoped that efforts like this will further our understanding of the important dimensions of performance, for example robustness or versatility as opposed to problem-specific efficiency. Participants to last year's competition have also noticed that it is fun to participate.

The competition is open to anyone.
The organisers would like to invite *anybody*,
including contestants, to submit problems and benchmarks.
Each of these problems will be made available
on the competition web-site, which may be found at:

However, to avoid possible biases, an independant jury will decide which problems will be used for the final evaluation.http://cpai.ucc.ie/06/Competition.html.

Contestants are co-ordially invited
to submit solvers, problems, and benchmarks.
Contestant may enter the competition with one or two solvers per main categories (CSP/Max-CSP, complete/incomplete).
Contestants are expected to
submit their solver(s) and contribute ten instances.
They may also submit a position paper (at least 3 pages) in a second stage.
The exact details are described in
the section entitled *Submission Process*,
which may be found further on.

This section briefly describes the rules and regulations for the solver competition. There are some restrictions about the kinds of constraint networks that will be allowed. The organisers have decided to introduce these restrictions for two reasons:

- The threshold for entering the competition should be kept as low as possible; and
- The complexity of running the competition should be kept manageable.

The following are the rules and regulations.
The competition allows
*competition compliant* CSPs only.
For the purpose of this year's competition
*competition compliant* will mean the following:

- Constraints will be crisp.
- This year the following types of constraints are allowed:
- constraints with extensional finite domain numeric relations.
- constraints with intensional algebraic or Boolean relations.
- the unique global constraint
*allDifferent*.

- Domains will include values that are in the range
-2147483648 to 2147483647 only.
Such values can be represented
using a four-byte
`int`in`C`. - Constraint relations will have positive arities.

**Important:** anyone can submit a solver that only deals with a subset of the types of constraints mentioned above.
For example, it is possible to submit a solver that only accepts binary constraints, constraints in extension, etc.

Any solver that can solve competition compliant CSPs can be submitted.

- Only one
*standard input format*will be allowed. Contestant are allowed to use a*conversion script*for transforming a standard input format to their preferred input format. The time taken for the transformation will not be counted as solution time. The organisers provide tools for parsing problems in standard specification format. The tools may be downloaded from

`http://www.cril.univ-artois.fr/~lecoutre/research/tools/tools.html`. - Contestants will
register and submit their solver(s),
submit ten instances, and
submit later a position paper describing the main
details of their solver.
Further requirements for participating
are described in the section
entitled
*Submission Process*, which may be found further on. - For each submitted solver, a contestant will provide all
files which are necessary to run the solver. Solvers may be
submitted either as source, or as a 32-bits Linux executable
(preferably statically linked). Contestants will provide the command line that should be used to run their solver during the submission process.
For solvers which don't read natively the XML format, a

*conversion script*may be submitted. It is used for transforming a problem in*standard input format*to a user-defined input format. - There will be CSP, solver, and problem specific categories.
Details about the categories are described in
the section entitled
*Categories*, which may be found further on.

This year there will be only one standard specification format.
This format is described in the document entitled
*XML Representation of Constraint Networks*, which may be found at
`http://cpai.ucc.ie/06/Representation.pdf`, and the document entitled
*Format Rules introduced for the
Second International CSP Solver Competition*, which may be found at `http://cpai.ucc.ie/06/Rules.pdf`.

Tools are provided to parse the problem descriptions in standard
specification format. The tools will provide hooks for
converting the problem description to a problem description in
the contestant's preferred specification format. The tools may
be downloaded from
`http://www.cril.univ-artois.fr/~lecoutre/research/tools/tools.html`.
The tools are also described in the document `http://cpai.ucc.ie/06/toolsV4.pdf`. The
conversion process and the restrictions to it are outlined in the
section entitled *Preprocessing*, which may be found further
on.

Neng-Fa Zhou has implemented a converter from `CLP( FD )` to
`XML`. The tool may be found at
`http://www.probp.com/solvers/`.

Compared to last year, there are a few changes.

- The format has changed. More information about this may be found in the format specification document.
- New constraints are allowed. More information about this may be found in the format specification document.
- Unary constraints are now also included (e.g.
`zebra.xml`). - It is possible to have
several constraints with the same scope
(e.g.
`fapp01-0200-0.xml`). - It is now possible to have constraints whose scopes are permutations.
- Constraint relations may be empty
(e.g.
`bqwh-15-106-0-ext.xml`).

For each combination of CSP, solver, and problem category,
there will be a ranking of solvers.
The categories are described in the section entitled
*Categories*, which may be found further on.
The main criteria for ranking the solvers
are as follows.

**Ordinary-CSP:**- Solvers claiming incorrect results will be disqualified. Of the remaining solvers, the solver solving the most problems will be declared the winner. Ties will be broken by considering the minimum total solution time.
**MAX-CSP:**- Solvers claiming incorrect results will be disqualified.
The remaining solvers will be ranked according to the following:
**Incomplete solvers**- will be ranked in increasing order of their average relative error (i.e. the average normalized difference between the cost of solutions found by the solver and the cost of the best known solutions).
**Complete solvers**- will be ranked in decreasing order of the number of instances for which a solution has been proved to be OPTIMUM. To break ties, we will rank the solvers in increasing order of their average relative errors.

This section describes how the organisers will offer problems to the solvers.

Problems are offered in standard input format only. They
may be *converted* to the contestant's preferred format.
Finally the problem will be solved. The precise details of these
phases are as follows:

**Copy phase:**- For each run, a temporary directory will be
created and all files submitted for this solver (conversion
script, executable, configuration files,...) will be copied to
this temporary directory. This directory will become the home
directory for the solver (which means that it may be accessed
as
`${HOME}`or with the notation). The problem in standard input format will be copied into the contestant's home directory as`unknown.xml`. Once the solver has completed its execution, the temporary directory will be erased. This means that for each run, the solver will be started with a brand new home directory and no data can be saved from one execution of the solver to another. Solvers are not allowed to use files outside of their home directory. **Preprocessing phase:**- This phase is for transforming
problems from standard input format to the contestant's
preferred input format. It will occur only if a
conversion script was submitted during the solver
submission and is done as follows. The conversion script
will be run with the command line registered during the
submission process. The conversion script will be allowed
to run to completion if it stays within the specified time
and memory limits, and will be terminated otherwise. There
are some restrictions about the nature of the conversion
scripts. For example, they are not allowed to record
non-trivial problem properties. Also they have to be
certified by the organisers. More information about the
nature of the conversion script and the certification
process are described in the section entitled
*Preprocessing*, which may be found further on. **Solution phase:**- In this phase the problems will be solved.
This is done as follows. The contestant's
`solver`script will be run with the command line registered during the submission process. The`solver`will be allowed to run to completion if it stays within the specified time and memory limits, and will be terminated otherwise.Solvers will be allowed to use no more than 900MiB of virtual memory. This limitation will ensure that two solvers can run concurrently on a 2GiB RAM, bi-processor computer without interaction. The actual memory limitation that is enforced is available in the MEMLIMIT environment variable (and command line parameter).

Solvers will be allowed to run for at least 20 minutes of CPU time. We expect to allow CSP solvers to run for 30 minutes and MAX-CSP solvers for 40 minutes but this limit depends on the number of solvers that will be submitted. The actual time limitation that is enforced is available in the TIMEOUT environment variable (and command line parameter).

Note that in combination with the preprocessing step the process should allow the contestant to use a problem specification in standard input format or the contestant's preferred input format. More details about the requirements for the

`solver`script are described in the section entitled*Solver Script*, which may be found further on. **Evaluation phase:**- In this phase the organisers will
evaluate the outcome of the solution phase. They will
check and record any solution which is output, they will
record the solution time, and they will record
*diagnostics*, which are described in the section entitled*Diagnostics*, which may be found further on.

Contestants are allowed to transform a problem specification
from standard input format
to their solver's native format.
To ease the task of parsing problem descriptions
in standard input format the organisers provide
tools for parsing.
The tools may be downloaded from
`http://www.cril.univ-artois.fr/~lecoutre/research/tools/tools.html`.
The tools are described in the document at `http://cpai.ucc.ie/06/toolsV4.pdf`.

Each of the following rules applies.

- The preprocessing time is not counted as solution time.
- Problem transformations are
*not*allowed. For example, transforming a problem to a SAT instance is not allowed as part of the preprocessing step. Such transformation should be carried out at solution time. - It is
*not*allowed to record any property of the input constraints/relations which is not specified explicitly in the input. For example, it is not allowed to record that a given constraint relation is universal or max-closed. Detecting such properties should be done at solution time. - A
*maximum of ten minutes*will be allowed for converting from standard input format. Any problem for which the conversion tool of a contestant requires more than ten minutes will be considered unsolvable for that contestant's solver. The conversion script will be imposed the same memory limit as the solver. - The conversion tool has to be
*certified*by the organising committee. To get their script certified, contestants should send their conversion scripts by email to Marc van Dongen (`dongen@cs.ucc.ie`) using the subject line*Competition: Conversion Script Certification Request*. Only certified conversion scripts will be allowed. - Contestants will submit their certified conversion script
together with their solver files. They will be asked
during the submission process to provide the command line
that should be used to run their conversion script. The conversion of the problems will be carried
out by the organising committee as part of the evaluation
process. To convert the problem called
`unknown.xml`they will do the following:- They will
copy the file
`unknown.xml`into the directory`${HOME}`. - Next they will run the conversion script as with the command line specified during the submission of the solver.

- They will
copy the file
- The conversion script may generate any number of files
specifying the problem in the contestant's preferred
format, provided the names of these files are not equal
to
`unknown.xml`and all files are created in the`${HOME}`directory (or in a subdirectory).

The evaluation environment that is used has some abilities which were not anticipated at the time of the first call for solvers. To get the full benefit of these capabilities, your solver should follow some different input/output rules than what was first advertised.

Specifically, the evaluation environment records everything that is output by your solver on stdout (up to a limit of 1MiB) and is able to timestamp each line. This can be very informative to check how your solvers behaved on some instances.

**Switching to the new rules should be easy but if you don't want to
change your solver, you are not required to use these new rules and
you may keep following the old ones.**

Here is a short description of the initial and new rules. A detailed description is available in sections 8.1 and 8.2.

- Initial rules:
Basically, your answer should be written to a file named

`${HOME}/solution`. The details are given in section 8.1. - New rules:
Basically, these rules say that your solver must give its answer on stdout (instead of using the

`${HOME}/solution`file). To be able to identify the solver answer between all the lines that your solver may output, some rules must be obeyed.Your solver must

- prefix the answer (SAT/UNSAT) with the two characters 's ' (s as solution).
No other line may begin with these two characters.
- prefix the model (in case of a satisfiable instance) with the two characters 'v ' (v as values). No other line may begin with these two characters.

Optionally, your solver may prepend all other lines with 'c ' (c as comment) (this is encouraged)

There are also some specific rules for MAX-CSP solvers as described in the following subsections.

- prefix the answer (SAT/UNSAT) with the two characters 's ' (s as solution).
No other line may begin with these two characters.

**You are free to choose the output format that you find more
convenient. The evaluation environment will support both formats.**

8.1 Initial rules

Restrictions about the nature of the solver scripts are described in the remainder of this section.

The first restriction is that it is not allowed to output different solutions for the same problem: if solutions and are output as solutions to a given problem then and should be equal. This restriction has been introduced to (1) prevent solvers from learning from previous problems, and (2) to ease the task of validation. As a consequence of this restriction, seeds of randomised solvers may have to be fixed depending on the input problem.

Regardless of the satisfiability of the problem,
the solver script should return an exit status of zero.
The solver script will only output a non-zero exit
status in the event of an exception.
The solver script will output the result of the solution process
to the file called `${HOME}/solution`.
This year there are two CSP categories: ordinary-CSP and MAX-CSP.
The following describes the rules for outputting solutions for
each of these categories.

**CSP:**- If the problem is unsatisfiable then:
- The solver script will output the word
`UNSAT`on its own on the first line of the file`${HOME}/solution`. - It may output diagnostics
on further lines of the file
`${HOME}/solution`. Diagnostics are used to provide information about the work which has been carried out by the solver. They are described in the section entitled*Diagnostics*, which may be found further on. - The solver script will return an exit status of zero.

- The solver script will output
the word
`SAT`on its own on the first line of the file`${HOME}/solution`. - It will output the solution
on the second line of the file
`${HOME}/solution`. Here the solution is a sequence of numbers (only), which are separated by one or more space symbols. The th number in the solution corresponds to the ``assignment'' to the th variable of the problem in the*original*problem specification in standard input format. (Note that this may have consequences for solvers that introduce auxilliary variables, rename variables, or change their order.) - The solver script may output diagnostics to the file
`${HOME}/solution`*after*the line containing the solution. The organisers will save up to a maximum of ten lines of diagnostics per problem. - The solver script will return an exit status of zero.

- The solver script will output the word
**MAX-CSP:**- For MAX-CSP the process is slightly different.
- For each solution found during the solving process, the
solver script will output the word
`SOL`on a new line of the file`${HOME}/solution`followed by one or more space symbols and a sequence of numbers (only), which are separated by one or more space symbols. The th number in the solution corresponds to the "assignment" to the th variable of the problem in the original problem specification in standard input format. (Note that this may have consequences for solvers that introduce auxilliary variables, rename variables, or change their order.). Each solution line must be ended by a line feed character ('n'). It is advised that you flush the output stream each time a new solution is added to the solution file. - If the optimality of the last found solution is proved by
the MAX-CSP solver, the solver script will output the
word
**OPTIMUM**on a new line of the file`${HOME}/solution`. - It may output diagnostics on further lines
of the file
`${HOME}/solution`. Diagnostics are used to provide information about the work which has been carried out by the solver. They are described in the section entitled Diagnostics, which may be found further on. - Unless killed, the solver script will return an exit status of zero.
- For MAX-CSP solvers, only the last complete solution line written to the solution file will be considered (i.e. the last line ended by a line feed character).

- For each solution found during the solving process, the
solver script will output the word

- First the organisers will copy the file
`unknown.xml`to`${HOME}/unknown.xml`. - Next the organisers will run the solver script as
`${HOME}/solver unknown time`.- If the solver script crashes, takes more time
than the maximum allowed solution time or uses
more memory than allowed then they will kill
the process running the script and the problem
will be considered
*unsolved*. - Otherwise,
if the solver script
(1) outputs
a solution for an unsatisfiable problem,
(2) claims there are no solutions to a satisfiable problem,
(3) outputs a wrong solution,
(4) outputs a syntactically incorrect solution line, or
(5) does not output
`SAT`or`UNSAT`on the first line of the solution file then the problem will be considered*solved incorrectly*and the solver will be disqualified. - Otherwise,
the problem will be considered
*solved correctly*and the solution time for that problem will be recorded. - In addition, up to ten lines of diagnostics will be recorded.

- If the solver script crashes, takes more time
than the maximum allowed solution time or uses
more memory than allowed then they will kill
the process running the script and the problem
will be considered

8.2 New rules

Solvers must output messages to the standard output and those messages will be used to check the results. The output format is inspired by the DIMACS output specification of the SAT competition and may be used to manually check some results.

Lines output by the solver should be prefixed by "c ","s ","v ", "d " or "o ". Lines which do not start by one of these prefixes are considered as comment lines and are ignored. The meaning of these prefixes is detailed below:

There exist 5 different types of lines. They are defined as follows:

- comment ("c " line)
Such lines start by the two characters: lower case c followed by a space (ASCII code 32). These lines are optional and may appear anywhere in the solver output. They contain any information that authors want to output. They are recorded by the evaluation environment for later viewing but are otherwise ignored. At most one megabyte of solver output will be recorded. So, if a solver is very verbose, some comments may be lost.

Submitters are advised to avoid outputing comment lines which may be useful in an interactive environment but otherwise useless in a batch environment. For example, outputing comment lines with the number of constraints read so far only increases the size of the logs with no benefit.

If a solver is really too verbose, the organizers will ask the submitter to remove some comment lines.

- diagnostic ("d " line)
These lines start by the two characters: lower case d followed by a space (ASCII code 32). Then, a keyword followed by a value must be given on this line. See section 9 for details about the diagnostics.

- values ("v " line)
These lines start by the two characters: lower case v followed by a space (ASCII code 32) and followed by a solution of the problem.

Here, a solution is a sequence of numbers (only), which are separated by one or more space symbols. The th number in the solution corresponds to the ``assignment'' to the th variable of the problem in the

*original*problem specification in standard input format. (Note that this may have consequences for solvers that introduce auxilliary variables, rename variables, or change their order.) - solution ("s " line)
These lines start by the two characters: lower case s followed by a space (ASCII code 32). These two characters are followed by one of the following answers:

- SATISFIABLE (used for CSP and MaxCSP)
- UNSATISFIABLE (used for CSP)
- UNKNOWN (used for CSP and MaxCSP)
- OPTIMUM FOUND (used for MaxCSP)

It is of uttermost importance to respect the exact spelling of these answers. Any mistake in the writing of these lines will cause the answer to be disregarded. Solvers are not required to provide any specific exit code corresponding to their answer.

See Subsections 8.2.2 and 8.2.3 about their use.

- objective cost ("o " line)
These lines start by the two characters: lower case o followed by a space (ASCII code 32). These two characters are followed by one integer.

See Subsection 8.2.3 about its use.

**Important:**
Any line must be terminated by a Line Feed character (the usual Unix line terminator 'n').
A "v " line which does not end with that terminator will be ignored because it will be
considered that the solver was interrupted before it could
output a complete solution.
Also, it is important that you don't forget to flush the output as soon as you have printed a "s " line or a "v " line.

8.2.2 Specific rules for CSP Solvers

A CSP solver must output exactly one "s " line (it is mandatory) and in addition, when the instance is found SATISFIABLE, exactly one "v " line. These lines are not necessary the first ones in the output since the CSP solver can output some "c " and "d " lines in any order. For a CSP solver, the "s " line must correspond to one of the following answers:

- s SATISFIABLE : when the solver has found a solution
- s UNSATISFIABLE : when the solver can prove that the instance has no solution
- s UNKNOWN : when the solver is not able to tell anything about the instance

If the solver does not output a "s " line, or if the "s " line is misspelled, then UNKNOWN will be assumed. For a CSP solver, the "v " line provides a valuation of each variable that satisfies all constraints. This will be used to check the correctness of the answer

8.2.3 Specific rules for MAX-CSP solvers

Since a MAX-CSP solver will not stop as soon as it finds a solution but instead will try to find a better solution, it must be given a way to output the best solution it found even when it reaches the time limit. There are two options depending on your ability to intercept signals. The first option may be used if your solver is able to catch the signal SIGTERM which will be sent by the evaluation environment at the time out and just two seconds before the solver is actually killed by a SIGKILL. This is the preferred option. The second option should be used when the first option is inapplicable.

- You can intercept signals:
Whenever your MaxCSP solver finds a better solution (or simply the first one) during search, it must output an "o " line with the current number of satisfied constraints (it is mandatory). Then, if your solver finds an optimal solution and proves its optimality (i.e., it can prove that no other assignment of the variables will satisfy more constraints than this one) then it must output a "s " line with OPTIMUM FOUND, followed by a "v " line containing the optimal solution. If your solver is interrupted, then it must output a "s " line with SATISFIABLE, followed by a "v " line containing the best found solution (keep in mind that you have only two seconds to do this).

This option saves some time as the solver avoids to output a certificate for each solution it found. It only outputs a certificate for the best solution which it was able to find.

Examples of C/C++ code to intercept the SIGTERM signal are available on the PB06 web site:

`http://www.cril.univ-artois.fr/PB06/coding.html`. Although this page gives code which is not directly suitable for the CSP competition, it should be straightforward to adapt it. - If you can't (or don't want to) catch the SIGTERM signal:
Then all you have to do is to output a "s " line with SATISFIABLE when the first solution is found, and a certificate "v " line each time you find a solution which is better than the previous ones (we also encourage you to output an "o " line although this is not mandatory). Only the last complete certificate will be taken into account. If eventually, your solver proves that the last solution that was output is optimal, then it must output a new "s " line with OPTIMUM FOUND.

Example: a solver (that can intercept signal) first finds a solution which satisfies only one constraint, then finds another solution which satisfies 4 constraints. At last it finds a solution which satisfies 17 constraints. Some time later, it proves that no better solution exists and it outputs "s OPTIMUM FOUND" followed by the solution which satisfies the 17 constraints. The output of this solver will be

o 1 o 4 o 17 s OPTIMUM FOUND v 1 4 7 8 3 4

The evaluation environment will automatically timestamp each of these lines so that it is possible to know when the solver has found a better solution and how good the solution was. The goal is to analyse the way solvers progress toward the best solution. The timestamped output will be:

0.57 o 1 1.23 o 4 2.7 o 17 10.5 s OPTIMUM FOUND 10.51 v 1 4 7 8 3 4

The first column in this example is the time at which the line was output by the solver (expressed in seconds of wall clock time since the beginning of the program).

A solver which doesn't intercept the SIGTERM signal may output for the same problem

c Got a first solution ! s SATISFIABLE o 1 v 1 1 1 1 1 1 c Found a better solution o 4 v 1 2 1 1 1 1 c Found a better solution o 17 v 1 4 7 8 3 4 s OPTIMUM FOUND

9 Diagnostics

A *diagnostic* describes the work carried out by the solver
scripts. They may be written to the file `${HOME}/solution` or
output on stdout as a 'd ' line (depending of the output rules
which you follow).

Each diagnostic is a line of the form `CLASS value`, where ` CLASS` is a sequence of letters describing the diagnostic's class,
and `value` is a sequence of characters defining the
diagnostic's value. The following classes are predefined:

`CHECKS`:- The total number of
*consistency checks*which have been carried out. `SAC_CHECKS`:- The total number of
*singleton arc consistency checks*which have been carried out. `NODES`:- The total number of
*visited nodes*in the search tree. Here a visited node corresponds to an explicit assignment of a value to a variable.

To cope with the different kinds of CSPs, solvers and constraints they can handle, contestants can enter the competition in different solver or problem categories.

There are two CSP categories: *ordinary-CSP* and
*MAX-CSP*.
The objective for ordinary-CSPs is finding a solution or deciding that no solution exists.
The objective for
MAX-CSPs is
finding an assignment to the variables that violates as
few constraints as possible.

The solver categories are
*complete*, for complete solvers and
*incomplete* for incomplete solvers.

The problem categories are

**extensional-binary:**- for extensional problems with only binary constraints.
**extensional-nonbinary:**- for extensional problems with both binary and non-binary constraints.
**intensional-binary:**- for intensional problems with only binary constraints.
**intensional-nonbinary:**- for intensional problems with both binary and non-binary constraints.
**allDifferent:**- for problems with
*allDifferent*constraints only.

Benchmarks in this year's standard input format may be found at

The organisers are particularly interested in new problem instances originating from real-world applications.http://www.cril.univ-artois.fr/~lecoutre/research/benchmarks/benchmarks.html.

The submission process has changed since the first publication of the call for solvers because we use another cluster which is unfortunately inaccessible from the internet (and this is really out of the control of the organizers). To submit their solvers, contestants will have to upload their files to the competition web site. See:

http://www.cril.univ-artois.fr/CPAI06/registration

Here is how to proceed:

- constestant will first request a login on the competition web
site. See:
`http://www.cril.univ-artois.fr/CPAI06/registration` - within a few hours, a login and password will be sent by
email
- with this login and password, contestants will be able to log in to the web site and submit their solvers.

Solvers should be submitted either in source form, or as a Linux 32 bits executable (preferably statically linked). Even if the cluster used has 64 bits processors, all solvers will run in 32 bits mode and we won't accept any 64 bits executable.

The upload form will ask contestant to give

- the name of the solver
- the version number of the solver
- the authors names
- the command line to use to run the solver.

Some keywords will have special meanings on this command line:

- HOME will stand for the directory where the uploaded files will reside
- BENCHNAME will stand for the name of the XML file (with its extension)
- BENCHNAMENOEXT will stand for the name of the XML file (without the .xml extension)
- TIMEOUT will stand for the maximum time given to solver (in seconds)
- MEMLIMIT will stand for the maximum memory that the solver may use (in MiB)
- RANDOMSEED stands for a random seed to be used by the solver

Examples:

- For a solver which follow the initial rules, the command line will be
HOME/solver BENCHNAMENOEXT TIMEOUT

- For a solver written in C, named mysolver which accepts as only
parameter the name of the instance file (with the .xml extension),
you will indicate
HOME/mysolver BENCHNAME

- For a solver written in C, named mysolver which accepts 3 parameters: the name of the instance file (without the .xml extension), the timeout and the
memory limit, you will indicate
HOME/mysolver BENCHNAMENOEXT TIMEOUT MEMLIMIT

- Same example, with a different syntax
HOME/mysolver --timeout=TIMEOUT --memlimit=MEMLIMIT BENCHNAMENOEXT

- For a solver written in Java, named mysolver you may write
java -Xms200M -Xmx600M -jar HOME/mysolver.jar BENCHNAME

- (optional) Solvers which require a conversion script will have to
provide the command line that must be used to run the conversion
script. This command line uses the same keywords as the solver command
line.
- the kind of solver which is submitted (ordinary-CSP or MAX-CSP as well as
complete/incomplete solver)
- the list of categories of instances which the solver is able to solve binary, N-ary, extension, intension, global constraints).
- some optional comments
- the name of the file to upload (if you want to submit several files for a solver, use an archive (tar file)). All files which are necessary to run the solver (conversion script, interpreters, configuration files, ...) must be submitted in an archive. An archive should contain only one solver.

Contestants are allowed to submit up to two solvers in each of the four main categories (CSP-complete, CSP-incomplete, MaxCSP-complete, MaxCSP-incomplete).

A preliminary test phase will allow the solvers to run on a *limited* number of benchmarks (only a few hundreds). Solvers which do
no conform to the input/output rules or are found buggy during this
test phase will be returned to their authors. They will be given one
week to fix the problem and re-submit their solver.

It is recalled that contestants are allowed to
convert any problem specification in standard format to
their solver's native format.
This is done by their *conversion script*,
which has to be approved by the organisers.
To get their conversion script approved by the organisers,
contestants will send their script/program to
Marc van Dongen (`dongen@cs.ucc.ie`) using the
subject line *Competition: Conversion Script Certification Request*.

One of the main problems in organising last year's competition has been to collect interesting problems. This is the main reason why it is now expected that each contestant contribute at least ten benchmark problems in the competition's problem specification format. These problems will be kept secret from the other contestants. It is guaranteed that ten of the submitted problems will be used during the evaluation phases of the competition. However, because of time constraints and possible biases, there is no guarantee that all submitted instances will be used during the competition.

To submit their contestants submitted problems, contestants should
upload an archive on the submission web site (`http://www.cril.univ-artois.fr/CPAI06/registration`).

These instances will be made available on the competition web site after the competition.

**December 5, 2006**: Solver and problem submission deadline for the second round.

Main Organizers:

- Marc van Dongen,
`dongen@cs.ucc.ie`, University College Cork, Ireland. - Christophe Lecoutre,
`lecoutre@cril.univ-artois.fr`, Université d'Artois, France. - Olivier Roussel,
`olivier.roussel@cril.univ-artois.fr`, Université d'Artois, France. - Radoslaw Szymanek,
`r.szymanek@4c.ucc.ie`, Cork Constraint Computation Centre, Ireland.

Other members of the organising committee:

- Fred Hemery,
`hemery@cril.univ-artois.fr`, Université d'Artois, France. - Chris Jefferson,
`Chris.Jefferson@comlab.ox.ac.uk`, University of Oxford. - Rick Wallace,
`r.wallace@4c.ucc.ie`, Cork Constraint Computation Centre, Ireland.

The following links may be useful.

- Solver Competition:
`http://cpai.ucc.ie/06/Competition.html`. - Registration form and competition results:
`http://www.cril.univ-artois.fr/CPAI06` - CPAI'06:
`http://cpai.ucc.ie/06/CPAI.html`. - CP'06:
`http://www.sciences.univ-nantes.fr/cp06/`. - Association for Constraint Programming:
`http://slash.math.unipd.it/acp/`

The organising committee wishes to thank the following sponsors.

- The CRIL (Centre de Recherche en Informatique de Lens) of Université d'Artois is providing a cluster for the evaluation.
- The Association for Constraint Programming is financially supporting the competition with 1000 Euros.

Second International CSP Solver Competition

(

Held in conjunction with

Twelfth International Conference on Principles and

Practice of Constraint Programming (CP'06)

Nantes, France

This document was generated using the
**LaTeX**2`HTML` translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.

Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.

The command line arguments were:

**latex2html** `-split 0 -nonavigation -show_section_numbers COMPETITION.tex`

The translation was initiated by Olivier Roussel on 2006-11-17

Olivier Roussel 2006-11-17