2017 XCSP3 Competition
Rules and available instances
Detailed results
The slides of the presentation at CP 2017 are available.
The detailed results of the different tracks are available below:
List of solvers in the competition
- AbsCon-basic (Christophe Lecoutre) solver description, executable used for the competition
- BTD (Philippe Jégou, Hanan Kanso, Cyril Terrioux), solvers description
- choco-solver (Charles Prud'homme and Jean-Guillaume Fages)
- Concrete 3.4 (Julien Vion) sources on github, solver description, executable used for the competition
- cosoco 1.12 (Gilles Audemard) solver description
- Mistral-2.0 2017-07-28 (Emmanuel Hebrard and Mohamed Siala) solver description, sources used for the competition
- Naxos 1.1.0 (Nikolaos Pothitos) solver description, sources on github, sources used for the competition
- OscaR (OscaR Team) sources on bitbucket, solvers description
- sat4j-CSP 2017-07-05 (Daniel Le Berre, Emmanuel Lonca) solver description, executable used for the competition, home page
Resources allocated to solvers and other details
-
The cluster we used is provided
by CRIL and is
composed of nodes with two quad-cores Intel(R) Xeon(R) X5550 @ 2.67GHz with
32 GiB RAM. Hyperthreading was disabled for the final runs.
-
Sequential solvers were run on one processor (4 cores) and were
allocated 15500 MiB of memory. Two instances of the same solver
were run simultaneously on one host.
- Parallel solvers were run on two processors (8 cores) and were
allocated 31000 MiB of memory.
- For Java programs, the -Xmx parameter was set to 11000 for
sequential solvers, and 22000 for parallel solvers. This parameter
was specified only when the author specified it on the command
line. These parameters allow to stay safely within the memory
limit.
-
In order to facilitate comparison, solvers which were run with the
same time limit and on a same set of instances were run in the same
event (group of tracks). Three events have been defined:
- Main tracks: CSP and COP, sequential and parallel solvers
with a 40 minutes time limit
- Fast COP tracks: COP, sequential and parallel solvers with a 4
minutes time limit
- Mini-solvers tracks: CSP and COP, sequential solvers with a
40 minutes time limit on a restricted set of instances
-
The time limit can be understood either as a CPU limit, or as a
wall-clock (WC) limit. Sequential solvers are best compared with a
CPU time limit. If it is assumed that CPU cores come for free
(which is quite a strong assumption), parallel solvers are best
compared with a WC time limit. Of course sequential and parallel
solvers which were run with the same limits can be compared, and
this can be quite informative.
In order to reach these two limits with a single run, solvers were
given a time limit augmented by 5% to give them a chance to reach
both limits. This was done only in tracks with both sequential and
parallel solvers. The results are post processed to enforce the
initial limit of the track and obtain the final ranking. The
limits given to solvers are summarized in the following table:
| Solver type | CPU limit | WC limit | Memory limit |
|---|
| sequential | track limit*1.05 | track limit*1.05 | 15500 MiB |
| parallel | track limit*nbCores*1.05 | track limit*1.05 | 31000 MiB |
-
The first solvers in the main event were run on nodes where
hyperthreading was randomly activated and the CPU frequency was
not necessarily set to its maximum, which prevents from comparing
safely the solvers. These very first runs were kept for
information, but otherwise ignored in the competition. They
correspond to solver names starting with R1 (as "Run 1") in the
main event.
Details of instances selection
After a few iterations, the jury has decided how many instances
should be selected in each series and has transmitted an Excel file
(selectionList-final.xls). Their
numbers have been merged with the list of instances in the
file selection-input.txt. Then, select.cc
has been compiled and run on a Fedora 23, with glibc 2.22.18.fc23 to
obtain the final random selection
(selection-output.txt).
After the first run, it was discovered that some selected instances
did not respect the XCSP3 format (e.g. duplicate values in domains)
and some other instances did not respect the restrictions of the
competition (e.g. forbidden constraints such as those using * in
tables, and the variant allDifferent-list). It was decided to fix
these problems as much as possible.
Out of the 1013 instances initially selected by the jury, 117 were either
reformulated (and given new names) to match the restrictions of the
competition or modified (with the same names) to respect the XCSP
format. 23 instances could not be reformulated and were
discarded. In the end, 990 instances were selected: 480 COP and 510
CSP (in the mini-solver track: 191 COP and 270 CSP, 461 instances in
total).
After contestants were able to check their own solver(s) results, it
was reported that several instances should not appear in the
selection (because they contain constraints which are not allowed by
the call for solvers).
The list of forbidden instances has been updated, and forbidden
instances were removed from the competition. The final numbers of
instances are : 439 COP and 510 CSP in the main tracks (949 in
total), 117 COP and 242 CSP in the mini-solver track (359 in total).
The list of instances which were replaced can be found
in xcsp17-substitutions.txt. The
list of instances which were removed from the main tracks can be
found
in xcsp17-removed-main.txt. The
list of instances which were removed from the mini tracks can be
found
in xcsp17-removed-mini.txt.
The lists of removed instances also contain the list of reformulated
instances.
Concerning the modification of problems, ten problems were modified,
mainly as indicated above because the instances contained table
constraints with short tables (containing *), or a a variant of
nValues encoding notAllEqual (which is not in the scope of the
restrictions imposed by the competition) or allDifferent-list.
These problems are:
-
ChessboardColoration: notAllEqual (nValues) replaced by
quaternary intensional constraints. Same number of instances.
-
CoveringArray: a variant of channel currently not in the
specifications reformulated as constraints element. Same number
of instances, but names have been slightly modified to avoid any
confusion.
-
Crossword: allDifferentList constraints have been
removed. Same number of instances, but names have been slightly
modified to avoid any confusion.
-
OpenStacks. The compiler has been slightly modified in order to
generate valid instances, and short tables converted into
ordinary tables. One instance has been removed (because it was
impossible to generate it). Names have been slightly modified
to avoid any confusion. The series m1(c) has been discarded
because it contains a variant of constraint element which is not
accepted (element with a vector of integers).
-
Rack. Short tables converted into ordinary tables.
-
Ramsey. nValues (notAllEqual) reformulated as ternary
intensional constraints. Same number of instances.
-
Scheduling-os-taillard. This is a series that replaces the
previous one because in some domains there were some values
duplicated. Same number of instances and same names.
-
SchurrLemma. notAllEqual reformulated as intensional
constraints.
-
SteelMillSlab. This is a series that has been discarded because
it contains a variant of constraint element which is not
accepted (element with a vector of integers).
-
Warehouse. This is a series that has been discarded because it
contains a variant of constraint element which is not accepted
(element with a vector of integers).
-
Wwtpp. Short tables converted into ordinary tables. Same number
of instances, but names have been slightly modified to avoid any
confusion.
Note that you can find the Java class
org.xcsp.checker.CompetitionChecker
on github
that can be run to check if an instance can be selected for a
standard track and a minisolver track.