Held in conjunction with CPAI'05 and CP'2005

Sitges, Spain

Index: |
## IntroductionAs part of the CPAI'05 workshop, which is held in conjunction with CP'05, there will be a CSP solver competition. With this competition we intend to further some of the goals of the workshop. Hopefully, it will allow us 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. We also hope 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.
The competition is open to anyone.
We co-ordially invite contestants
to submit solvers and benchmarks.
Each contestant is allowed to submit [ Back to index ] ## ProgrammePlease follow this link for a printer-friendly programme. [ Back to index ] ## ProceedingsThis year's CPAI proceedings consist of two volumes. Volume I covers the "regular" part of the workshop. Volume II covers the First International Solver Competition. Participants of the workshop will receive a printed version of Volume I and will recieve Volume II on a DVD. The DVD also contains Volume I and all the problems that were used for the First International CSP Solver Competition. [ Back to index ] ## Rules and regulationsThis section briefly describes the rules and regulations for the solver competition. Since this is the first time we are organising such a competition there are some restrictions about the kinds of CSP that will be allowed. The organising committee 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. - We will only allow
**competition compliant**and**binary competition compliant**CSPs. For the purpose of this year's competition*competition compliant*will mean the following:- There will be no objective functions.
- Constraints will be crisp.
- Constraints will have extensional finite domain numeric relations.
- Domains will include values that are in the range
-16384 –16384 , (-2 ^{14}– 2 ) only. Such values can be represented using a four-byte^{14}`int` in`C` . - Constraint relations will have arities
in the range
2 –20 only. Note that this rule**excludes**unary constraints. - The scopes of any two different constraints will differ.
*Binary competition compliant*CSPs are competition compliant CSPs whose constraints have an arity which is equal to two. - Any solver that can solve competition compliant or binary competition compliant constraint satisfaction problems can be submitted.
- Only standard input formats will be allowed. Contestant are allowed to install a conversion script to transform a standard input format to their preferred input format. The time taken for the transformation will not be counted as solution time. More information about the standard input formats and the conversion script may be found below.
- Contestants must register their solver. After registering, they will receive a user name and an account for the machine that will be used for the evaluation. They will use their account to install their solver in their home directory on that machine. Tools and test problems will be provided to test the installation.
- Each contestant will provide
two Bourne shell scripts for a solver in their home directory.
The first script is called the
**conversion script**. It will be used for transforming a problem in standard input format to a user-defined input format. The second script is called the**solver script**. It will be used to solve the problem. The conversion script should be installed as`${HOME}/conversion` for the first solver (`${HOME}/conversion2` for the second solver). The solver script should be installed as`${HOME}/solver` for the first solver and (`${HOME}/solver2` for the second solver). More information about the nature of the conversion and solver scripts may be found in the section entitled Evaluation, which may be found below. - There will be solver and problem specific categories.
[ Back to index ] ## Format specification
There will be two standard problem formats.
The first is a problem specification in
Each problem description
will define a unique
Each standard problem specification format
be stored in files having a unique
[ Back to index ] ## EvaluationThis section describes the evaluation process.
Problems will be described in
standard input formats only.
For each problem with
basename The evaluation process consists of the following three phases. **Preprocessing phase:**This phase is for transforming problems from one of the standard input formats to the contestant's preferred input format. This is done as follows. For each problem with basename`basename` , the input files for`basename` will be copied into the contestant's home directory. Next the contestant's certified conversion script will be run as`${HOME}/conversion basename` for the first solver (`${HOME}/conversion2 basename` for the second solver). Finally, the input files for`basename` will be deleted from the contestant's home directory. More information about the nature of the conversion script and the certification process may be found below.**Solution phase:**In this phase the problems will be solved. This is done as follows. For each problem with basename`basename` , the input files for`basename` will be copied into the contestant's home directory. Next the contestant's`solver` script will be run as`${HOME}/solver basename` for the first solver (`${HOME}/solver2 basename` for the second solver). Finally, the input files for`basename` will be deleted from the contestant's home directory. Note that in combination with the preprocessing step this should allow the contestant to use any standard input format or the contestant's preferred input format. More details about the requirements for the`solver` script may be found below.**Evaluation phase:**
In this phase the organising committee
will evaluate the outcome of the
solution phase.
More information about the exact rules for
the evaluation will be made available shortly.
[ Back to index ] ## PreprocessingContestants are allowed to transform a problem specification from one of the standard input formats to their own format. Each of the following rules apply. - The transformation time is not be 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 that is not specified explicitly in the input. For example, it is not allowed to record that a given constraint relation is max-closed. Detecting this should be done at solution time. - A
**maximum of five minutes**will be allowed for converting from standard input format. Any problem for which the conversion tool of a contestant requires more time than the maximum allowed time will be considered unsolvable for that contestant's solver. - The conversion tool has to be
**certified**by the organising committee. To get their script approved, contestants should send their conversion scripts by email to dongen@cs.ucc.ie using the subject line**"Request for conversion script certification"**. Only certified conversion scripts are allowed. - Contestants will install
their certified conversion script as
`${HOME}/conversion` for the first solver (`${HOME}/conversion2` for the second solver), where`${HOME}` is their home directory. The conversion of the problems will be carried out by the organising committee. To convert the problem with basename`basename` they will do the following:- They will
copy the input files for
`basename` into the directory`${HOME}` . - Next they will run the conversion script as
`${HOME}/conversion basename` for the frist solver (`${HOME}/conversion2 basename` for the second solver). - Finally, they will remove the input files for
`basename` from the directory`${HOME}` .
- They will
copy the input files for
- The conversion script may generate any number of files specifying the problem in the contestant's preferred format, provided the extensions of these files differ from the extensions of the standard input formats.
[ Back to index ] ## Solver script
Each contestant will install an executable
called
Regardless of the satisfiability of the problem,
the solver script will always return an exit status of zero
(this rule has changed since the first call).
The solver script is only allowed to return a non-zero exit
status in the event of an exception.
If the problem with
basename - Will output the word
**UNSAT**by its own on the first line of standard output (`stdout` ). - May output
**diagnostics**on standard output. Diagnostics are defined further below. - Will return an exit status of zero.
If the problem with
basename - Will output the word
**SAT**by its own on the first line of standard output (`stdout` ). - Will output the
**solution**on the second line of standard output. Here the*solution*is a sequence of numbers only. The*i*th number in the solution will correspond to the ``assignment'' to the*i*th variable in any standard input specification of the problem with basename`basename` . - May output diagnostics
**after**the line containing the solution. The organising committee will save up to a maximum of ten lines of diagnostics per problem. - Will return an exit status of zero.
To solve the problem with
basename - First they will copy the
input files
for
`basename` into`${HOME}` . - Next they will run the solver script as
`${HOME}/solver basename` for the first solver (`${HOME}/solver2 basename` for the second solver).- If the solver script takes more time than
the maximum allowed solution time
then they will kill the script and the
problem will be considered
**unsolved**. - Otherwise,
if the solver scripts outputs
a solution for an unsatisfiable problem,
outputs a wrong solution,
outputs a syntactically incorrect solution line,
or returns a non-zero exit status for
a satisfiable problem then
the problem will be considered
**solved incorrectly**. - Otherwise,
the problem will be considered
**solved correctly**and the solution time for that problem will be recorded. For satisfiable problems the solution will also be recorded. In addition, up to ten lines of diagnostics will be recorded.
- If the solver script takes more time than
the maximum allowed solution time
then they will kill the script and the
problem will be considered
- Finally,
they will remove the input files for
`basename` from`${HOME}` .
[ Back to index ] ## Diagnostics
A **CHECKS:**The total number of**consistency checks**that were carried out.**NODES:**(For complete methods only) The total number of**nodes opened**during search. There are now competing definitions of search nodes due to the interpretation of instantiation of variables with singleton domains. In order to facilitate comparisons, we would like contestants whose solvers make this measurement to adhere to the following guidelines.- Nodes should include all assignments made during search (basic decision points).
- If variables with singleton domains are instantiated 'automatically' whenever they occur, the number of such instantiations should be recorded and added to the total.
[ Back to index ] ## CategoriesThere will be a number of special solver categories (incomplete solvers, complete solvers, …). Also there will be categories for different kinds of problems (binary, non-binary, random, quasigroup problems with holes, …). More precise information about the diffent solver and problem categories will be provided shortly.[ Back to index ] ## BenchmarksLink to the problem benchmarks page. [ Back to index ] ## Tools and TestingA tool called checker allows validating and converting table and XML representations of CSP instances. It can be downloaded at this page . For more information about this tool, see checker.html . Information about some other tools will be provided shortly. [ Back to index ] ## ExampleAn example may be found by following the following link. [ Back to index ] ## How to enter? Submission of solvers is open to anyone.
Contenstants are expected to
register for the solver competition.
To register,
they are invited to send an email
to dongen@cs.ucc.ie
from May 3 on
using the subject line [ Back to index ] ## Important dates- May 3, 2005: Solver registration/installation opening.
- July 21, 2005:
**Extended deadline:**Solver registration/installation closing. - July 31, 2005:
**Extended deadline:**Paper submission deadline. - August 14, 2005: Acceptance notification.
- August 1, 2005: Early CP registration deadline.
- September 7, 2005: Camera-ready version deadline.
[ Back to index ] ## Competition organising committee
- Frédéric Boussemart, Université d'Artois, France. (boussemart@cril.univ-artois.fr)
- Fred Hemery, Université d'Artois, France. (hemery@iut-gtr.univ-artois.fr)
- Mark Hennessy, Cork Constraint Computation Centre, Ireland. (m.hennessy@4c.ucc.ie)
- Deepak Mehta, Cork Constraint Computation Centre, Ireland. (dm6@student.cs.ucc.ie)
- Christophe Lecoutre, Université d'Artois, France. (lecoutre@cril.univ-artois.fr)
- Radoslaw Szymanek, Cork Constraint Computation Centre, Ireland. (r.szymanek@4c.ucc.ie)
- Marc van Dongen, Cork Constraint Computation Centre, Ireland. (dongen@cs.ucc.ie)
- Rick Wallace, Cork Constraint Computation Centre, Ireland. (r.wallace@4c.ucc.ie)
- Yuanlin Zhang, Texas Tech University, USA. (yzhang@cs.ttu.edu)
[ Back to index ] ## Sponsors
- The Cork Constraint Computation Centre is generously offering CPU time, storage space, and system administrator's time.
[ Back to index ] |