Call for CSP Solvers and CSP Benchmarks


October 1, 2005

First International Constraint Satisfaction Solver Competition
Held in conjunction with CPAI'05 and CP'2005
Sitges, Spain


Index:

 Introduction 

 Programme 

 Proceedings 

 Rules 

 Formats 

 Evaluation 

 Preprocessing 

 Solver script 

 Diagnostics 

 Categories 

 Benchmarks 

 Tools 

 Example 

 How to enter? 

 Dates 

 Organisation 

 Sponsors 


 CPAI'2005 

Introduction

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 ]

Programme

Please follow this link for a printer-friendly programme.

Back to index ]

Proceedings

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 ]

Rules and regulations

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 -1638416384, (-214214) only. Such values can be represented using a four-byte int in C.
    • Constraint relations will have arities in the range 220 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 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 ]

Evaluation

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 ]

Preprocessing

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:
    1. They will copy the input files for basename into the directory ${HOME}.
    2. Next they will run the conversion script as ${HOME}/conversion basename for the frist solver (${HOME}/conversion2 basename for the second solver).
    3. 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 ]

Solver script

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:

  1. First they will copy the input files for basename into ${HOME}.
  2. 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.
  3. Finally, they will remove the input files for basename from ${HOME}.

Back to index ]

Diagnostics

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 ]

Categories

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 ]

Benchmarks

Link to the problem benchmarks page.

Back to index ]

Tools and Testing

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 ]

Example

An 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 "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 ]

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