Call for Solvers and Benchmarks
Second International CSP Solver Competition
(http://cpai.ucc.ie/06/Competition.html)
Held in conjunction with
Twelfth International Conference on Principles and
Practice of Constraint Programming (CP'06)
http://www.sciences.univ-nantes.fr/cp06/
Nantes, France

Marc van Dongen
Christophe Lecoutre
Olivier Roussel
Radoslaw Szymanek
Fred Hemery
Chris Jefferson
Rick Wallace

Abstract:

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.


Contents

1 Introduction

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.

2 Scope

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:

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

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.

3 Rules and Regulations

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:

  1. The threshold for entering the competition should be kept as low as possible; and
  2. The complexity of running the competition should be kept manageable.
The organising committee intends to gradually relax these restrictions in the coming years.

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:

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.

4 Format Specification

4.1 Main Details

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/.

4.2 Changes

Compared to last year, there are a few changes.

5 Ranking

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.

6 Evaluation

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 $\sim$ 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.

7 Preprocessing

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.

8 Solver Script

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.

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


8.1 Initial rules

Each contestant will install an executable called ${HOME}/solver in their home directory ${HOME}. This executable is called the solver script. To solve the problem unknown.xml this script will be run as ${HOME}/solver unknown time, where time is the maximum solution time in seconds which is given to the solver.

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 $X$ and $Y$ are output as solutions to a given problem then $X$ and $Y$ 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.
If the problem instance is satisfiable then:
  • 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 $i$th number in the solution corresponds to the ``assignment'' to the $i$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.
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 $i$th number in the solution corresponds to the "assignment" to the $i$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 ('$\backslash$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).
To solve the problem unknown.xml the organisers will do the following:
  1. First the organisers will copy the file unknown.xml to ${HOME}/unknown.xml.
  2. 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.


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:

8.2.1 Lines

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

Important: Any line must be terminated by a Line Feed character (the usual Unix line terminator '$\backslash$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:

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.

  1. 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.

  2. 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.
Contestants wishing to record other diagnostics than the ones listed before should inform Marc van Dongen (dongen@cs.ucc.ie) about the names and nature of the diagnostics.

10 Categories

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.

10.1 CSP 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.

10.2 Solver Categories

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

10.3 Problem Categories

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.

11 Benchmarks

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

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

12 Submission Process

12.1 Solver Submission Process

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:

  1. constestant will first request a login on the competition web site. See:
    http://www.cril.univ-artois.fr/CPAI06/registration

  2. within a few hours, a login and password will be sent by email

  3. 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

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.

12.2 Conversion Script Certification Process

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.

12.3 Problem Submission Process

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.

13 Important Dates for the Competition

14 Organising Committee

Main Organizers:

Other members of the organising committee:

15 Links

The following links may be useful.

16 Sponsors

The organising committee wishes to thank the following sponsors.

About this document ...

Call for Solvers and Benchmarks
Second International CSP Solver Competition
(http://cpai.ucc.ie/06/Competition.html)
Held in conjunction with
Twelfth International Conference on Principles and
Practice of Constraint Programming (CP'06)
http://www.sciences.univ-nantes.fr/cp06/
Nantes, France

This document was generated using the LaTeX2HTML 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