|
Index:
Introduction
Programme
Proceedings
Rules
Formats
Evaluation
Preprocessing
Solver script
Diagnostics
Categories
Benchmarks
Tools
Example
How to enter?
Dates
Organisation
Sponsors
CPAI'2005
|
As 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 two solvers.
Contestants are expected to (a) submit a short paper (3 to 5 pages)
to the CPAI'05 workshop
about the main implementation details of their solver or
(b) submit a regular paper (between 5 and 15 pages) with
a more detailed description of their solver.
In addition they are expected to fill out a questionnaire.
The results of the competition will be evaluated
at the CPAI'05 workshop.
At least one author of each accepted submission
must attend the workshop.
However, this requirement may be relaxed for short (3 to 5 page) papers describing the
implementation of a solver submitted to the competition.
[ Back to index ]
Please follow this link
for a printer-friendly programme.
[ Back to index ]
This 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 ]
This 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.
Hopefully,
we can learn from
the experience of organising this year's competition.
The organising committee intends to
gradually relax the restrictions in coming years.
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,
(-214–214)
only.
Such values can be represented
using a four-byte
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 ]
There will be two standard problem formats.
The first is a problem specification in
XML format.
A formal description of this format may be
found by following this
link.
The second specification is in
table format.
A formal description of this format may be
found by following this
link.
Each problem description
will define a unique
basename,
which is a short character sequence.
When submitting benchmarks, the basename should convey some information
about the nature of the problem.
However,
when running the competition, the basename will be modified
to ? so that it doesn't
convey any information about the nature of that problem.
Each standard problem specification format
be stored in files having a unique
extension.
Problem specifications in XML format will
be stored in files with
extension .xml.
Problem specifications in table format
be stored in files with extension .txt.
[ Back to index ]
This section describes the evaluation process.
Problems will be described in
standard input formats only.
For each problem with
basename basename
and for each standard input format with
extension ext
there will be file called
basename.ext describing the problem
with basename basename in
that standard input format.
The collection of all files
in standard input format describing the problem
with basename basename will be called
the input files for
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 ]
Contestants 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}.
- 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 ]
Each contestant will install an executable
called ${HOME}/solver for the first solver
(${HOME}/solver2 for the second solver) in their
home directory ${HOME}.
This executable is called the
solver script.
To solve the problem with
basename
basename
this script will be run as ${HOME}/solver basename for the first solver
(${HOME}/solver2 basename for the second solver).
There are no restrictions about the nature of the solver script,
provided it outputs exit statuses and solutions as specified
in the following paragraphs.
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 basename
is unsatisfiable
then the solver script:
- 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 basename
is satisfiable
then the solver script:
- 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 ith number in the solution will correspond
to the ``assignment'' to the ith 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 basename
the organising committee will do the following:
- 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.
- Finally,
they will remove the input files for
basename from
${HOME}.
[ Back to index ]
A Diagnostic
is a line describing the search process.
Diagnostics should be output on standard output only.
Each diagnostic is 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 class is predefined
(more classes will follow shortly):
- 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 ]
There 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 ]
Link to the problem benchmarks page.
[ Back to index ]
A 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 ]
An example may be found by following the following
link.
[ Back to index ]
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 "Solver Registration".
They will then be given a username and an account
for the machine that will be used for the final evaluation,
where they can install their solver.
Contestants will also be contacted by the organising committee
to provide some basic information about
their solver and which
categories they wish to enter.
Contestants are expected to submit a paper
to the
CPAI'05 workshop
outlining the main implementation details of their solver.
Each contestant is allowed to submit up to three
benchmark problems
in one of the standard input formats.
These problems will be added to
the problems that will be used for the final evaluation.
[ Back to index ]
- 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
|