The Wayback Machine - https://web.archive.org/web/20060813201559/http://www.cril.univ-artois.fr:80/~lecoutre/research/benchmarks/benchmarks.html

Benchmarks 2.0
XML representation of CSP instances



Presentation CSP instances Research

Presentation

In two domains of artificial intelligence, namely, satisfiability testing (SAT) and planning, one can benefit from a standard description of problem instances. Indeed, SAT and planning instances are usually described using respectively a format called DIMACS and a definition language called PDDL.

On the other hand, the domain of constraint satisfaction does not benefit from such a standard. Hence, reproducing instances of the Constraint Satisfaction Problem (CSP) introduced in the literature currently requires a significant development effort. This is the reason why we propose a format using XML to represent CSP instances.

This format, identified as XCSP 2.0, is described in the following document. It allows to represent both constraints defined in extension and in intention. Whereas random instances only involve constraints defined in extension, most of the structured instances given below are represented with constraints in intention.However, when the space required to represent constraints in extension is reasonable, it is possible to convert constraints in intention into constraints in extension. It suffices to use the tool instanceChecker described here.

When generating instances, we take care of following some naming conventions:

If you want to generate some new benchmarks, we suggest that you follow, as much as possible, these rules.

June 15, 2006. See below, new FAPP and Pseudo-Boolean series.
June 23, 2006. See below, Random instances of various network density and constraint tightness.
July 12, 2006. See below, Multi-Knapsack, Job-Shop and Open-Shop Instances.
July 31, 2006. See below, bqwh and pigeons series involving the global allDifferent constraint. Also, see two series of instances involving positive table constraints of large arity.


CSP instances

In the table below, you can find different CSP instances. Click on the series, to download the corresponding instances.

Problem Series #Instances Arity Satisfiability Description
Forced instances
of Model RB		 frb30-15 5*2 2 all sat Here are 8 sets of 5(*2) random CSP instances of model RB forced to be satisfiable. These instances are particularly interesting as they are hard to solve. For more information about model RB and forced satisfiable instances, see:
[Xu-Li, Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research 12, 2000]
[Xu-Boussemart-Hemery-Lecoutre, A simple model to generate hard satisfiable instances, IJCAI'05]
For more information about these instances, see this link.
Note that for each instance, there is a file representing the original instance and another one representing the same instance after merging constraints with similar scope.
frb35-17 5*2 2 all sat
frb40-19 5*2 2 all sat
frb45-21 5*2 2 all sat
frb50-23 5*2 2 all sat
frb53-24 5*2 2 all sat
frb56-25 5*2 2 all sat
frb59-26 5*2 2 all sat
Unforced and forced instances
of Model RB		 2-30-15 50 2   Here are 12 sets of 50 random CSP instances of model RB studied in:
[Xu-Boussemart-Hemery-Lecoutre, A simple model to generate hard satisfiable instances, IJCAI'05]
2-30-15 forced 50 2 all sat
2-40-19 50 2  
2-40-19 forced 50 2 all sat
2-50-23 50 2  
2-50-23 forced 50 2 all sat
3-20-20 50 3  
3-20-20 forced 50 3 all sat
3-24-24 50 3  
3-24-24 forced 50 3 all sat
3-28-28 50 3  
3-28-28 forced 50 3 all sat
Chessboard Coloration chessboardColoration 20 4   This is the chessboard coloration problem where all squares of a chessboard composed of r rows and c columns must be colored.
There are exactly n available colors and the four corners of any rectangle extracted from the chessboard must not be assigned the same color.
Golomb Ruler golombRulerArity3 14 2 - 3 7 sat
7 unsat 		This is the Golomb Ruler problem instance where a ruler of length l must contain n marks.
See prob006 at http://www.csplib.org
golombRulerArity4 14 4 7 sat
7 unsat
Sat ehi-85 100 2 all unsat These are two sets of 100 unsatisfiable 3-SAT instances converted to binary CSP instances using the dual method.
See [Bacchus, Extending forward checking, CP'00].
See [Lecoutre-Boussemart-Hemery, Backjump-based techniques versus conflict-directed heuristics, ICTAI'04].
ehi-90 100 2 all unsat
bqwh bqwh-15-106 100 2 all sat These are two sets of satisfiable balanced quasi-group instances with holes.
See [Gomez-Shmoys, Completing quasi-groups or latin squares: astructured graph coloring problem].
See [Boussemart-Hemery-Lecoutre-Sais, Boosting systematic search by weighting constraints, ECAI'04].
Instances "_glb" contain the global allDifferent constraint.
bqwh-18-141 100 2 all sat
bqwh-15-106_glb 100 > 2 all sat
bqwh-18-141_glb 100 > 2 all sat
Travelling Salesman Problem travelling Salesman 20 15 3 all sat The Travelling Salesperson problem is the task, given a set of cities, of finding a tour of minimal length that traverses each city (only once). Two series of 15 ternary instances (all sat) have been generated by Radoslaw Szymanek for the 2005 competition.
travelling Salesman 25 15 3 all sat
Hanoi hanoi 5 2 all sat This is the Hanoi towers problem.
Latin Square latinSquare 10 2   This is the Latin square problem.
All rows and columns of a matrix must contain different values (taken from 0 to n-1).
Here, all diagonals (including broken ones) must also contain different values.
Queen Attacking queenAttacking 10 2   See prob029 at http://www.csplib.org
Queens queens 14 2 all sat The well-known queens problem.
Knights knights 19 2   The knights problem.
Queens Knights queensKnights 18 2 all unsat This is a Queens-Knights problem where, on a chessboard of size n*n, q queens and k knigths must be placed.
See [Boussemart-Hemery-Lecoutre-Sais, Boosting systematic search by weighting constraints, ECAI'04].
RLFAP scens 11 2   This is the Radio Link Frequency Assignment Problem (RLFAP).
See [Cabon-deGivry-Lobjois-Schiex-Warners, Radio Link Frequency Assignment, Constraints 4(1), 1999].
Three series correspond to instances for which some constraints have been deleted or/and some frequencies removed as described in: [Bessiere-Chmeiss-Sais, Neighborhood-based variable ordering heuristics for the constraint satisfaction problem, CP'01].
graphs 14 2  
scens11 10 2  
scensMod 14 2  
graphsMod 14 2  
FAPP fapp01-05 11*5 2   The Frequency Assignment Problem with Polarization constraints (denoted FAPP) is the problem retained for the ROADEF'2001 challenge . It is one extended subject of the CALMA European project.
fapp06-10 11*5 2  
fapp11-15 11*5 2  
fapp16-20 11*5 2  
fapp21-25 11*5 2  
fapp26-30 11*5 2  
fapp31-35 11*5 2  
fapp36-40 11*5 2  
test01-04 11*4 2  
Job-Shop e0ddr1 10 2 all sat Here are 5 sets of 10 job-shop CSP instances studied in:
[Sadeh-Fox, Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem, Artificial Intelligence 86, 1996]
I would be very grateful if someone could send me the two missing sets (enddr2 and ewddr1) in their original forms (as the corresponding files that are currently available are corrupted).
e0ddr2 10 2 all sat
enddr1 10 2 all sat
enddr2 6 2 all sat
ewddr2 10 2 all sat
Renault renault 1 2-10 sat This is a CSP instance from Renault that was converted from symbolic to numeric domains.
Cril cril 8     This is the contestant series submitted by abscon challengers to the 2005 competition.
Geom geom 100 2 92 sat
8 unsat 		This is the series generated by Rick Wallace for the 2005 competition.
Marc marc 10 2 5 sat
5 unsat 		This is the contestant series submitted by Marc van Dongen to the 2005 competition.
Ramsey ramsey3 8 3   This is the problem of colouring the edges of a complete graph with n nodes using k colors.
See prob017 at http://www.csplib.org
ramsey4 8 3  
Pigeons pigeons 25 2 all unsat This is the problem of putting n pigeons into n-1 boxes, one pigeon per box.
Instances "_glb" contain the global allDifferent constraint.
pigeons_glb 19 > 2 all unsat
All Interval Series series 25 2-3 all sat This is the problem of all-interval series.
See prob007 at http://www.csplib.org
Domino domino 24 2 all sat This is the domino problem introduced by:
[Zhang-Yap, Making AC3 an optimal algorithm, IJCAI'01]
Schurr's lemma schurrLemma 10 3   This is the Schurr's lemma problem.
See prob015 at http://www.csplib.org
The modified versions are introduced in:
[Bessiere-Meseguer-Freuder-Larossa, On Forward Checking for non binary constraint satisfaction, Artificial Intelligence 141, 2002]
Composed random 25-10-20 10 2 all sat Here are 9 classes of 10 random CSP instances such that each generated instance is composed of a main (under-constrained, here) fragment and some auxiliary fragments, each of which being grafted to the main one by introducing some binary constraints. Such classes have been introduced in:
See [Lecoutre-Boussemart-Hemery, Backjump-based techniques versus conflict-directed heuristics, ICTAI'04].
Related instances have been experimented in:
[Jussien-Debruyne-Boizumault, Maintaining arc consistency within dynamic backtracking, CP'00]
25-1-2 10 2 all unsat
25-1-25 10 2 all unsat
25-1-40 10 2 all unsat
25-1-80 10 2 all unsat
75-1-2 10 2 all unsat
75-1-25 10 2 all unsat
75-1-40 10 2 all unsat
75-1-80 10 2 all unsat
Random instances from Model B rand-2-23 10 2   Here are five original series of 10 random instances generated according to Model B. The instances were generated by Marc van Dongen for the 2005 competition.
rand-2-24 10 2  
rand-2-25 10 2  
rand-2-26 10 2  
rand-2-27 10 2  
Pseudo-Boolean instances aim 48 >2   Here are 20 series of non binary instances. These instances correspond to the Pseudo-Boolean instances that were used for testing solvers submitted to the Pseudo Boolean 2006 Evaluation 2006. However, note that objective functions have been removed and that some original instances are missing (we did not succeed in converting and validating very large instances).
For more information about the origin of these series, see:
chnl 21 >2  
circuits 7 >2  
course 4 >2  
fpga 36 >2  
garden 7 >2  
ii 41 >2  
jnh 16 >2  
logic-synthesis 17 >2  
mps 49 >2  
mpsReduced 106 >2  
niklas 19 >2  
par 30 >2  
ppp 6 >2  
primesDimacs 11 >2  
radar 12 >2  
routing 15 >2  
ssa 8 >2  
ttp 8 >2  
uclid 39 >2  
Random instances of various network density and constraint tightness <40,8,753,0.1> 100 2 51/49 Here are seven series of 100 binary random instances (generated following Model D) situated at the phase transition of search. For each class , the number of variables n has been set to 40, the domain size d between 8 and 180, the number of constraints e between 753 and 84 (and, so the density between 0.96 and 0.1) and the tightness t, which denotes the probability that a pair of values is allowed by a relation, between 0.1 and 0.9. The first class <40,8,753,0.1> corresponds to dense instances involving constraints of low tightness whereas the seventh one <40,180,84,0.9> corresponds to sparse instances involving constraints of high tightness. What is interesting here is that a significant sampling of domain sizes, densities and tightnesses is introduced.
<40,11,414,0.2> 100 2 53/47
<40,16,250,0.35> 100 2 48/52
<40,25,180,0.5> 100 2 50/50
<40,40,135,0.65> 100 2 52/48
<40,80,103,0.8> 100 2 47/53
<40,180,84,0.9> 100 2 47/53
Multi-Knapsack Instances mknap 6 >2   This is a series of Multi-Knapsack instances studied in:
[Refalo, Impact-based search strategies for Constraint Programming, CP, 2004]
[Cambazard-Jussien, Identifying and exploiting problem structures using explanation-based Constraint Programming, Constraints, 2006]
Job-Shop and Open-Shop Instances js-taillard-15 30 2   These are some series of Job-Shop and Open-Shop instances generated (by Julien Vion) according to [Taillard, Benchmarks for basic scheduling problems, European journal of operations research, 1993].
Here, instances are only considered for satisfaction. To do this, when considering the original optimization problem, we have set the time window to the best known value (100 occurring in the name of the instances), a smaller value (95 occurring in the name of the instances) and a greater value (105 occurring in the name of the instances). All "100" and "105" instances are satisfiable.
js-taillard-20-15 30 2  
js-taillard-20 30 2  
os-taillard-4 30 2  
os-taillard-5 30 2  
os-taillard-7 30 2  
os-taillard-10 30 2  
os-taillard-15 30 2  
os-taillard-20 30 2  
Positive Table Constraints rand-8-20-5 20 8 all sat These are two series of non binary instances involving positive table constraints.
They are given to illustrate [Lecoutre-Szymanek, Generalized Arc Consistency for Positive Table Constraints, CP'06].
rand-10-20-10 20 10 all unsat