XCSP 2.1: a format to represent CSP/QCSP/WCSP instances

We have introduced a new extended format, identified as XCSP 2.1, to represent constraint networks using XML. This format allows us to represent:

Each instance may involve:

You will find the description of the format XCSP 2.1 in this document. For the last competition, read the dedicated description of the format in this document.

Generating Instances in XCSP 2.1

The current format XCSP 2.1, adopted for the 2008 and 2009 CSP/MaxCSP/WCSP solver competitions, allows us to represent global constraints and constraints defined in extension or in intension. Whereas random instances only involve constraints defined in extension, most of the structured instances given below are represented with global constraints or constraints defined in intension. However, when the space required to represent constraints in extension is reasonable, it is possible to convert constraints in intension into constraints in extension. It suffices to use the tool instanceChecker available from here.

There are some traps that must be avoided. Check that your solver has no problem with:

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, the rules given above.

Series of CSP instances

Once the format is defined, one has to propose some benchmarks to be used by the community. These two last years, we have collected a certain number of series of CSP instances from different backgrounds. At a first level, we can distinguish between structured instances and random instances (the more structured an instance is, the lower its entropy is). However, it may be interesting to refine categories of instances as follows:

Roughly speaking, we can consider that from top (REAL) to bottom (RAND), categories contain less and less structured instances. These categories may intersect with an additional category:

In tables below, you can find different series of CSP instances, collected so far. Click on the series, to download the corresponding instances. The column Type indicates how constraints are represented. It can be:

Also, some series are considered for:

Of course, this is quite subjective. It is not always immediate to classify some series. Any constructive remark is welcome.

REAL (Real-World Instances)

Problem Series #Instances Arity Satisfiability Type
BMC The bmc instances are bounded model checking problems which were converted from CNF to intensional CSP by Marc van Dongen. These instances are non-binary. The original instances may be found on SATLIB . For each SATLIB instance, CSP instances were generated for different domain sizes. For example, the original instance bmc-ibm-1.cnf was converted to instances bmc-ibm-1-2.xml, bmc-ibm-1-4.xml, bmc-ibm-1-8.xml and bmc-ibm-1-16.xml. The domain of the instance bmc-ibm-1-n.xml is given by {0,...,n-1}. All instances corresponding to a given original SAT instance are equivalent in the sense that their solutions are the same. This was achieved by adding unary constraints to remove values greater than 1. It was hoped that having different domain sizes would allow us to study the impact of the domain size on the solver efficiency. Indeed, some solvers that were able to solve a given instance with domain size 4 could not solve the same instance with domain size greater than 4. bmc 24 >2   INT
Cabinet This is an assignment scheduling problem where some tasks are processed on one, of a number of, machines. Depending on the machine chosen, a task may take a different amount of time to be processed. The objective is to assign all the tasks to machines in order to minimise the overall makespan. This is equivalent to minimising the maximum makespan of each machine. In these examples, the problem is presented as a satisfaction one, and involves the global constraint element. See [Darby-Dowman-Little-Mitra-Zaffalon, "Constraint Logic Programming and Integer Programming approaches and their collaboration in solving an assignment scheduling problem", Constraints, 1:3, 1997]. Note that the problem originally is an optimisation problem and comes from industry. The different instances are for different domain sizes of the variable which acts as the objective function. The instances cabinet-5560.xml - cabinet-5579.xml should be unsatisfiable, the remaining ones satisfiable. Instance cabinet-5580.xml corresponds to the optimal solution. This series has been kindly contributed by Leonid Ioffe and Kames Little from 4C, with the participation of Marc van Dongen. cabinet 40     GLB
Crossword Given a grid and a dictionary, the problem is to fulfill the grid with the words contained in the dictionary. Here, three series of grids (Herald, puzzle, Vg) and four dictionaries (lex, ogd, uk, words) have been used. Herald refers to crossword puzzles taken from the Herald Tribune (Spring, 1999), Puzzle refers to crossword puzzles mentioned in [Ginsberg, Dynamic Backtracking, JAIR, 93] and [Ginsberg et al., Search Lessons Learned from Crossword Puzzles, AAAI-90] and Vg refers to blank grids. Lex is a dictionary used in [Samaras-Stergiou, Binary encodings of non binary satisfaction problems: algorithms and experimental results, JAIR, 2005], Uk corresponds to the UK cryptic solvers dictionary, words corresponds to the dictionary found in /usr/dict/words under Linux and Ogd corresponds to a french dictionary. Lex and words are small dictionaries whereas Uk and Ogd are large ones. The model used to represent the instances is the one identified by m1 in [Beacham-Chen-Silito-vanBeek, Constraint Programming lessons learned from crossword puzzles, 2001]. However, for the Vg grids, all instances only involve constraints in extension as for these grids, putting two times the same word has been authorized. Thank you to Hadrien Cambazard, Kostas Stergiou and Julian Ullmann for their help. lexHerald 47 >2   EXT/INT
lexPuzzle 22 >2   EXT/INT
lexVg 63 >2   EXT
ogdHerald 50 >2   EXT/INT
ogdPuzzle 22 >2   EXT/INT
ogdVg 65 >2   EXT
ukHerald 50 >2   EXT/INT
ukPuzzle 22 >2   EXT/INT
ukVg 65 >2   EXT
wordsHerald 49 >2   EXT/INT
wordsPuzzle 22 >2   EXT/INT
wordsVg 65 >2   EXT
Driver These instances correspond to the WCSP instances located here with the same name. They have been converted and slightly modified to make them satisfiable. The name of all instances is prefixed by driverlogw. driver 7 2 all sat EXT
FAPP The Frequency Assignment Problem with Polarization constraints (denoted FAPP) is the optimization problem retained for the ROADEF'2001 challenge . It is one extended subject of the CALMA European project (Combinatorial ALgorithms for Military Applications). In this problem, one can find some constraints concerning the distance between frequencies and depending on their polarizations. For such constraints, a progressive relaxation is authorized: a relaxation level is possible between 0 (no relaxation) and 10 (the maximum relaxation). To obtain a decision problem, one has just to set one of these relaxation levels. In other words, 11 CSP instances can be defined from any original FAPP instance. Series of instances are denoted by fappNB with NB is in 01...40 while individual instances are denoted by fappNB-n-r where n is the number of variables and r is the relaxation level. The higher the value of r is, the less constrained the instance is. fapp01-05 11*5 2 30 sat
15 unsat		 INT
fapp06-10 11*5 2 27 sat
28 unsat		 INT
fapp11-15 11*5 2   INT
fapp16-20 11*5 2 16 sat
39 unsat		 INT
fapp21-25 11*5 2 25 sat
30 unsat		 INT
fapp26-30 11*5 2 27 sat
28 unsat		 INT
fapp31-35 11*5 2 29 sat
26 unsat		 INT
fapp36-40 11*5 2 33 sat
22 unsat		 INT
test01-04 11*4 2 21 sat
23 unsat		 INT
Renault This is a CSP instance obtained from a Renault Megane configuration problem that has been converted from symbolic domains to numeric ones. Interestingly, this instance (we have it under two forms, the first one is normalized and teh second one is not), denoted by renault, involve large table constraints of high arity. The series modifiedRenault contains instances generated from the original configuration one. These instances are interesting in studying, for example, GAC algorithms for table constraints. Thank you to Kostas Stergiou for having provided them. renault 2 2-10 sat EXT
modifiedRenault 50 2-10   EXT
RLFAP The Radio Link Frequency Assignment Problem (RLFAP) is the task of assigning frequencies to a number of radio links in such a manner as to simultaneously satisfy a large number of constraints and use as few distinct frequencies as possible. In 1993, the CELAR (the French ``Centre d'Electronique de l'Armement'') built a suite of simplified versions of Radio Link Frequency Assignment Problems starting from data on a real network. These benchmarks have been made available to the public in the framework of the European EUCLID project CALMA (Combinatorial Algorithms for Military Applications). For more information, see [Cabon-deGivry-Lobjois-Schiex-Warners, Radio Link Frequency Assignment, Constraints 4(1), 1999]. There are five series of binary RLFAP instances, identified as either scen or graph. Following the approach of [Bessiere-Chmeiss-Sais, Neighborhood-based variable ordering heuristics for the constraint satisfaction problem, CP'01], some modified RLFAP instances have been produced by removing some constraints (w followed by a value) and/or some frequencies (f followed by a value). For example, scen07-w1-f4 corresponds to the instance scen07 for which the constraints of weight greater than 1 have not been taken into account and the 4 highest frequencies have been removed. The last series "subs" is interesting for Max-CSP. scens 11 2 6 sat
5 unsat		 INT
graphs 14 2 8 sat
6 unsat		 INT
scens11 10 2 all unsat INT
scensMod 14 2 5 sat
8 unsat		 INT
graphsMod 14 2 6 sat
6 unsat		 INT
sub-instances 9 2 all unsat INT
Timetabling These instances come from the 2007/2008 timetabling competition as well as from the previous one in 2002. They involve the global constraint allDifferent as well as intensional constraints. These series have been converted and generated by Emmanuel Hebrard in the context of the 2008 CSP Solver Competition. small 5 >2 all sat GLB
medium 5 >2 all sat GLB
compet02 20 >2 all sat GLB
compet08 16 >2 all sat GLB

PATT (Patterned instances)

Problem Series #Instances Arity Satisfiability Type
Black Hole The Black Hole problem is the task of moving all cards of 17 fans of 3 cards each to the center pile, the Black hole, which initially only contains the Ace of Spades. Three series of instances (which correspond to a simplification of the original problem) have been generated by Radoslaw Szymanek for the 2005 CSP Solver Competition. They are denoted by blackHole-4-n with n in {4,7,13}. BH-4-4 10 2 all unsat EXT
BH-4-7 20 2   EXT
BH-4-13 7 2   EXT
BQWH 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-15-106 100 2 all sat EXT
bqwh-18-141 100 2 all sat EXT
bqwh-15-106_glb 100 >2 all sat GLB
bqwh-18-141_glb 100 >2 all sat GLB
Cril This is the contestant series submitted by abscon challengers to the 2005 competition. cril 8   1 sat
7 unsat		 EXT
Fischer This series correspond to Fischer SMT Instances from MathSat converted to CSP by Lucas Bordeaux. The translation is a straightforward encoding of the SMT syntax in which Boolean combinations of arithmetic constraints are decomposed into primitive constraints, using reification where appropriate. Note that the domains have been artificially bounded, whereas in SMT theorem proving should be done over the unbounded integers. fischer 121 3   INT
Graph Coloring The graph coloring problem can be stated as follows: given a graph G=(V,E), the objective is to find the minimum number of colors k such that there exists a mapping r from V to 1..k with r(i) <> r(j) for every edge (i,j) of G. The decision problem associated with this optimization problem involves determining if the graph can be colored when using a given number of colors k. All CSP instances given here have been built from resources that can be found here . We would like to thank very much Mickael Trick for kindly authorizing us to exploit the resources he has collected. Concerning the instances, some interesting results can be found in [Benhamou and Saidi, Local Symmetry Breaking During Search in CSPs, CP'07]. coloringExt 22 2   EXT
hos 14 2   INT
insertion 73 2   INT
leighton 68 2   INT
mug 8 2   INT
myciel 16 2   INT
register 149 2   INT
school 8 2   INT
sgb 120 2   INT
new Graph Isomorphism The subgraph isomorphism problem involves deciding if there exists a copy of a pattern graph in a target graph. More information about these instances can be found in [Solnon, AllDifferent-based filtering for subgrpah isomorphism, Artificial Intelligence 174 (12-13), 2010] classes 100   EXT/GLB
graphs-valiente 793   EXT/GLB
si2-bvg 360   EXT/GLB
si2-m4D 120   EXT/GLB
si2-rand 120   EXT/GLB
si4-bvg 360   EXT/GLB
si4-m4D 120   EXT/GLB
si4-rand 120   EXT/GLB
si6-bvg 360   EXT/GLB
si6-m4D 120   EXT/GLB
si6-rand 120   EXT/GLB
Haystacks The Haystacks instances are binary instances which were created by Marc van Dongen. All instances are unsatisfiable. The instances are parameterised by their size. Instance haystacks-n.xml is called the haystack instance of size n. It has n*n variables and each variable has domain {0,...,n-1}. The constraint graph is highly regular, consisting of n clusters: one central cluster and n-1 outer clusters. Each cluster is an n-clique. The outer clusters are connected to the central cluster by a single edge (constraint). The instances were designed such that if the variables in the central cluster have singleton domains, only one of the outer clusters contains an inconsistency --- this instance is the haystack. The instances were designed such that ``learning'' to locate the haystack from past experience is difficult. This was done as follows. The assignment to the variables in the central cluster determines which outer cluster is the haystack. Different assignments to the variables in the central cluster lead to different haystacks. The task then consists of finding the haystack and deciding that it is inconsistent, thereby providing a proof that the current assignment to the variables in the central cluster is invalid. If the structure of these instances isn't taken into account then solving them may take quite some time when the size becomes large. haystacks 51 2 all unsat INT
Job-Shop These problems are derived from classical job-shop scheduling problems by multiplying the number of jobs and the capacity of the resources (that is, the number of machines) by the given factor. The makespan value is also specified. For example, ft06x2-55.xml is obtained from ft10 multiplied by two with the makespan value 55. For more information, see this link , or/and consult [Laborie,"Complete MCS-based search: Application to resource constrained project scheduling", IJCAI-05], [Nuijten,"A computational study of constraint satisfaction for multiple capacitated job shop scheduling", European Journal of Operational Research, 90(2), 1996]. This series has been submitted by Naoyuki Tamura to the 2008 CSP solver competition and involves the global constraint cumulative. cjss 10 >2   INT/GLB
Job-Shop 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). e0ddr1 10 2 all sat INT
e0ddr2 10 2 all sat INT
enddr1 10 2 all sat INT
enddr2 6 2 all sat INT
ewddr2 10 2 all sat INT
Job-Shop and Open-Shop 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-15 30 2 20 sat
10 unsat		 INT
js-taillard-20-15 30 2 20 sat
10 unsat		 INT
js-taillard-20 30 2 20 sat
10 unsat		 INT
os-taillard-4 30 2 20 sat
10 unsat		 INT
os-taillard-5 30 2 20 sat
10 unsat		 INT
os-taillard-7 30 2 20 sat
10 unsat		 INT
os-taillard-10 30 2 20 sat
10 unsat		 INT
os-taillard-15 30 2 20 sat
10 unsat		 INT
os-taillard-20 30 2 20 sat
10 unsat		 INT
Multi-Knapsack Instances 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] mknap 6 >2 all sat INT
Open-Shop Two series of instances proposed by Naoyuki Tamura for the 2008 CSP Solver Competition (actually, the sat instances were proposed by Naoyuki Tamura for the 2006 CSP Solver Competition and corresponds to the old series). These series corresponds to open-shop instances developed by Christelle Guéret and Christian Prin. See this link . Problems are translated into CSP instances for the optimal makespans (sat instances) and the optimal makespan - 1 (unsat instances). os-gp-unsat 10 2 all unsat INT
os-gp-sat 10 2 all sat INT
Radar Surveillance Description is forthcoming. radar-8-24-3-2 50 >2   INT
radar-8-30-3-0 50 >2   INT
radar-9-28-4-2 50 >2   INT
Primes The Primes instances are non-binary intensional instances which were created by Marc van Dongen. All instances are satisfiable. The domains of the variables consist of prime numbers and all constraints are linear equations. The coefficients and constants in the equations are also prime numbers. These instances are interesting because solving them using Gausian elimination is polynomial, assuming that the basic arithmetic operartions have a time complexity of O(1). In reality this assumption does not hold and the choise of prime numbers in the equations gives rise to large intermediate coefficients in the equations, making the basic operations more time consuming. It was hoped this would allow to compare the trade-off between using a GAC approach on the original equations and the Gausian elimination approach. primes-10 32 >2 all sat INT
primes-15 32 >2 all sat INT
primes-20 32 >2 all sat INT
primes-25 32 >2 all sat INT
primes-30 32 >2 all sat INT
QCP/QWH The Quasi-group Completion problem (QCP) is the task of determining whether the remaining entries of the partial Latin square can be filled in such a way that we obtain a complete Latin square, ie. a full multiplication table of a quasi-group. The Quasi-group With Holes problem (QWH) is a variant of the QCP as instances are generated in such a way that they are guaranteed to be satisfiable. These 8 series of instances have been generated by Radoslaw Szymanek for the 2005 CSP Solver Competition. QCP-10 15 2 10 sat
5 unsat		 EXT
QCP-15 15 2 10 sat
5 unsat		 EXT
QCP-20 15 2 10 sat
5 unsat		 EXT
QCP-25 15 2 10 sat
5 unsat		 EXT
QWH-10 10 2 all sat EXT
QWH-15 10 2 all sat EXT
QWH-20 10 2 all sat EXT
QWH-25 10 2 all sat EXT
RCPSP This is the Resource Constrained Project Scheduling Problem. These satisfaction instances have been generated from data/instances of Baptiste and Le Pape (see this link) by Hadrien Cambazard with the help of Sophie Demassey. rcpsp 39 >2   INT+GLB
rcpspTighter 39 >2   INT+GLB
Super-solutions Problem These series of instances have been built by converting original problems into the corresponding "super-solutions" problems. That is, any solution of the resulting problem is a (1,0)-super solution of the original one. For more information about super-solutions and the encoding, see [Hebrard-Hnich-Walsh, Super-solutions in Constraint programming, CPAIOR'04]. Remark that it requires instances with large domains and a lot of solutions to produce interesting problems. Here, some scheduling benchmarks as well as some N-queens instances have been encoded since they match these criteria. These series have been converted and generated by Emmanuel Hebrard in the context of the 2008 CSP Solver Competition. super-jobshop (Sadeh) 46 2   INT
super-js (Taillard) 90 2   INT
super-os (Taillard) 180 2   INT
super-queens 14 2   INT
Two-Dimensional Strip Packing Problems These are the Two-Dimensional Strip Packing Problems by E. Hopper. See [Hopper, "Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods" PhD Thesis, Cardiff University, 2000]. Please refer the following OR-Library page for the problem description and to obtain original problems: Problems given in "strip1" are translated into CSP instances for the optimal height and the optimal height + 1. This series has been submitted by Naoyuki Tamura to the 2008 CSP solver competition. tdsp 42 >2   INT
Travelling Salesman Problem 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 20 15 3 all sat EXT
travelling Salesman 25 15 3 all sat EXT

ACAD (Academic instances)

Problem Series #Instances Arity Satisfiability Type
All Interval Series The all-interval series problem is the task of finding a vector s = (s_1, ..., s_n), such that s is a permutation of {0,1,...,n-1} and the interval vector v = (|s_2-s_1|, |s_3-s_2|, .... |s_n-s_{n-1}|) is a permutation of {1,2,...,n-1}. See prob007 at http://www.csplib.org. Each instance is denoted by series-n. series 25 2-3 all sat INT
BIBD Each BIBD (balanced incomplete block designs) instance is defined by a binary matrix with v rows, b columns, r ones per row, k ones per column and a scalar product lambda between any pair of distinct rows. Such instances have been experimented for example in [Meseguer-Torras, Exploiting symmetries within constraint satisfaction search, AIJ 2001], [Puget, Symmetry Breaking using Stabalizers, CP 2003], [Frish-Hnich-Kiziltan-Miguel-Walsh, Propagation algorithms for lexicographic ordering constraints, AIJ 2006]. Note that the model used here involves integrating (hidden) variables to be used for scalar products, which allows to introduce the global constraint weightedSum. See prob028 at http://www.csplib.org. Each instance is denoted by bibd-v-b-r-k-lambda_glb. bibd6 10 >2 all sat INT/GLB
bibd7 14 >2 all sat INT/GLB
bibd8 7 >2 all sat INT/GLB
bibd9 10 >2 all sat INT/GLB
bibd10-11 6 >2 all sat INT/GLB
bibd12-13 7 >2 all sat INT/GLB
bibdVariousK 29 >2 all sat INT/GLB
Chessboard Coloration The chessboard coloration problem is the task of coloring all squares of a chessboard composed of r rows and c columns. There are exactly n available colors and the four corners of any rectangle extracted from the chessboard must not be assigned the same color. Each instance is denoted by cc-r-c-n. chessboardColoration 20 4 10 sat
10 unsat		 INT
Costas Array A Costas array can be regarded geometrically as a set of n points lying on the squares of a n×n checkerboard, such that each row or column contains only one point, and that all of the n(n-1)/2 displacement vectors between each pair of dots are distinct. This result in an ideal 'thumbtack' auto-ambiguity function, making the arrays useful in applications such as Sonar and Radar. A Costas array may be represented numerically as an n×n array of numbers, where each entry is either 1, for a point, or 0, for the absence of a point. When interpreted as binary matrices, these arrays of numbers have the property that, since each row and column has the constraint that it only has one point on it, they are therefore also permutation matrices. Thus, the Costas arrays for any given n are a subset of the permutation matrices of order n. Costas arrays can be regarded as two-dimensional cousins of the one-dimensional Golomb ruler construction, and, as well as being of mathematical interest, have similar applications in experimental design and phased array radar engineering. All Costas arrays of size up to and including 26x26 are known. Costas arrays are known for infinitely many sizes because there exist two methods of generating them, both of which work near primes (of which there are infinitely many) and powers of primes. These are known as the Welch and Lempel-Golomb generation methods, and come from a branch of mathematics known as finite field theory. It is not known whether Costas arrays exist for all sizes. Currently, the smallest sizes for which no arrays are known are 32x32 and 33x33. This series has been generated by Emmanuel Hebrard. costasArray 11 >2   GLB
Domino This problem has been introduced in [Zhang-Yap, Making AC3 an optimal algorithm, IJCAI'01] to emphasize the sub-optimality of the algorithm AC3. Each instance, denoted domino-n-d, is binary and corresponds to an undirected constraint graph with a cycle. More precisely, n denotes the number of variables, the domains of which are {1,...,d}, and there exists n-1 equality constraints X_i = X_{i+1} (for all i in {1,...,n-1}) and a trigger constraint (X_1 = X_n+1 and X_1 < d) or (X_1 = X_n and X_1 = d). domino 24 2 all sat INT
Golomb Ruler The Golomb Ruler problem is the task of putting n marks on a ruler of length m such that the distance between any two pairs of marks is distinct. See prob006 at CSPLib. Each instance from the model involving ternary (resp. quaternary) constraints is denoted by ruler-m-n-a3 (resp. ruler-m-n-a4). golombRulerArity3 14 2 - 3 7 sat
7 unsat		 INT
golombRulerArity4 14 4 7 sat
7 unsat		 INT
Hanoi The problem of the towers of Hanoi is the task of transferring an entire tower represented by n disks initially stacked in increasing size on one of three pegs to one of the two other pegs, moving only one disk at a time and never a larger one onto a smaller. Each instance is binary, satisfiable and denoted by hanoi-n. hanoi 5 2 all sat EXT
Knights The knights problem. knights 19 2 all unsat INT
Langford The (generalized version of the) problem is to arrange k sets of numbers ranging from 1 to n, so that each appearance of the number m is m numbers on from the last. See prob024 at CSPLib. Each instance is denoted by langford-k-n. langford_ext 4 2 2 sat
2 unsat		 EXT
langford-2 24 2   INT
langford-3 24 2   INT
langford-4 24 2   INT
Latin Square 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. latinSquare 10 2   GLB
Orthogonal Latin Squares Two latin squares are orthogonal if each pair of elements in the same position occurs exactly once. For example:
1 2 3     1 2 3
2 3 1     3 1 2
3 1 2     2 3 1
are orthogonal. The most easy way to see this is by concatenating elements in the same position and verify that no pair appears twice:
11 22 33
23 31 12
32 13 21
There are orthogonal latin squares of any size except 1, 2, and 6 (see [Colbourn-Dinitz,"Mutually orthogonal latin squares: a brief survey of construction"]). The current model uses a third matrix z holding an integer identifying the pair in the corresponding position. Table constraints are used to link each pair with its identifier. Global constraints alldifferent are posted on each row and column of the two latin squares and on the full matrix z. This problem could also be modelled with element constraints instead of table. This series has been submitted by Marco Correia to the 2008 CSP solver competition. 		ortholatin 9 >2   GLB
Magic Square 18 instances from the well known magic square problem involving the global constraints weightedSum and allDifferent. magicSquare 18 >2   GLB
NengFa 10 instances proposed by Neng-Fa Zhou for the 2006 CSP Solver Competition. nengfa 10 >2   INT+GLB
Perfect Square Packing Consider the squares from size 1 x 1 to n x n. What is the smallest square that these n squares will fit into? This is an old question, dating back to Martin Gardner's column in Scientific American some 30 years ago. This sequence starts 1, 3, 5, 7, 9, 11, 13, 15, 18, 21, 24, 27, 30, 33, 36, 39, 43, 47, 51, 54, 58, 63, 67, 71, . . . and is A005842 of the Encyclopedia of Integer Sequences. It is a special case of problem 09 of csplib. These series have been generated by Hadrien Cambazard. Be careful: the instances initially posted have been modified (please, check that you have the last version - download series again if necessary - the old series contain 36 instances instead of 37). allsquares 37 >2   INT+GLB
allsquaresUnsat 37 >2   INT+GLB
Pigeons The Pigeons problem is the task of putting n pigeons into n-1 boxes, one pigeon per box. All instances are clearly unsatisfiable. Each instance is denoted by pigeons-n. Instances "_glb" contain the global allDifferent constraint. pigeons 25 2 all unsat INT
pigeons_glb 19 > 2 all unsat GLB
Queens The well-known queens problem. queens 14 2 all sat INT
largeQueens 5 2 all sat INT
Quasigroup Existence Quasigroup existence problems determine the existence or non-existence of quasigroups of a given size with additional properties. Certain existence problems are of sufficient interest that a naming scheme has been invented for them.
QG3.m problems are order m quasigroups for which (a*b)*(b*a) = a.
QG4.m problems are order m quasigroups for which (b*a)*(a*b) = a.
QG5.m problems are order m quasigroups for which ((b*a)*b)*b = a.
QG6.m problems are order m quasigroups for which (a*b)*b = a*(a*b).
QG7.m problems are order m quasigroups for which (b*a)*b = a*(b*a).
For each of these problems, we additionally demand that the quasigroup is idempotent. That is, a*a=a for every element a. See prob003 at CSPLib. This series has been generated by Emmanuel Hebrard. Note that the global constraint element is involved in these instances. 		QG3 7 >2   GLB
QG4 7 >2   GLB
QG5 7 >2   GLB
QG6 7 >2   GLB
QG7 7 >2   GLB
Queen Attacking The Queen Attacking problem is the task of putting a queen and the n^2 numbers 1,...,n^2, on a n*n chessboard so that no two numbers are on the same cell, any number i+1 is reachable by a knight move from the cell containing i and the number of cells containing a prime number that are not attacked by the queen is 0 (for satisfaction). See prob029 at CSPLib. Each instance is denoted by queenAttacking-n. queenAttacking 10 2 8 sat
2 unsat		 INT
Queens-Knights The Queens-Knights problem is the task of putting on a chessboard of size n*n, q queens and k knights such that no two queens can attack each other and all knights form a cycle (when considering knight moves). See [Boussemart-Hemery-Lecoutre-Sais, Boosting systematic search by weighting constraints, ECAI'04]. In one version of this problem (identified by ``add''), a square of the chessboard can be shared by both a queen and a knight and in another one (identified by ``mul''), it is not allowed. For the first version, each instance is denoted by queensKnights-n-k-add while for the second one, it is denoted by queensKnights-n-k-mul. queensKnights 18 2 all unsat INT
Ramsey The Ramsey problem is the task of coloring, using k colors, the edges of a complete graph involving n nodes in such a way that there is no monochromatic triangle in the graph (i.e., in any triangle at most two edges have the same color). See prob017 at CSPLib. Each instance is ternary and denoted by ramsey-n-k. ramsey3 8 3   INT
ramsey4 8 3   INT
Schurr's lemma The Schurr's lemma problem is the task of putting n balls labelled from 1 to n into 3 boxes so that for any triple of balls (x,y,z) with x+y=z, not all are in the same box. See prob015 at CSPLib. The series is prefixed by lemma and suffixed by mod for the variant proposed in [Bessiere-Meseguer-Freuder-Larossa, On Forward Checking for non binary constraint satisfaction, Artificial Intelligence 141, 2002]. schurrLemma 10 3   INT
Social Golfers This is a series of instances proposed by Daniel le Berre and Ines Lynce for the 2006 CSP Solver Competition. The original problem can be described by enumerating four constraints as follows: a) The golf club has 32 members. b) Each member plays golf once a week. c) Golfers always play in groups of 4. d) No golfer plays in the same group as any other golfer twice. It can be easily generalized. An instance to this geenralized problem is then characterized by a triple w-p-g, where w is the number of weeks, p is the number of players per group and g is the number of groups. The encoding used here is the one proposed by Walser and is available on CSPLIB. socialGolfers 12 >2   INT

QRND (Quasi-random instances)

Problem Series #Instances Arity Satisfiability Type
BDD These series have been generated by Kenil Cheng and Roland Yap in the context of the paper [Cheng and Yap, Maintaining Generalized Arc Consistency on ad-hoc n-ary Boolean constraints, ECAI'06]. The first series contains small BDD constraints and the second one large ones (a BDD constraint is a random extensional constraint built from a binary decision diagram). bddSmall 35 18   EXT
bddLarge 35 15   EXT
MDD The series half-n25-d5-e56-r7 consists of 25 random CSPs with semi-structural constraints. Each instance has 25 variables whose domain has 5 values; there are 56 7-ary positive constraints. To create a constraint, we first build an MDD in a post-order manner (sub-MDDs are made before the root node) - with 50% chance, a previously created sub-MDD is reused; otherwise, a new sub-MDD is created by expanding the current node recursively. The terminals are either true or false (50-50). In the second step, we enumerate all paths in the MDD to form the list of solutions (supports) of the extensional constraint. The series rand-n23-d3-e16-r15-t150000 consists of 25 random CSPs. Each instance has 23 variables whose domain has 3 values; there are 16 15-ary positive constraints with 150000 randomly generated solutions. Constraints may share same scope (didn't check). No structure was injected. These series have been submitted by kenil Cheng and Roland Yap to the 2008 CSP solver competition. half 25 7   EXT
rand 25 15   EXT
Composed 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: [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-10-20 10 2 all sat EXT
25-1-2 10 2 all unsat EXT
25-1-25 10 2 all unsat EXT
25-1-40 10 2 all unsat EXT
25-1-80 10 2 all unsat EXT
75-1-2 10 2 all unsat EXT
75-1-25 10 2 all unsat EXT
75-1-40 10 2 all unsat EXT
75-1-80 10 2 all unsat EXT
Ehi A 3-SAT instance is a SAT instance such that each clause contains exactly 3 literals. Two series of 3-SAT unsatisfiable instances have been converted into CSP instances using the dual method as described in [Bacchus, Extending forward checking, CP'00]. See [Lecoutre-Boussemart-Hemery, Backjump-based techniques versus conflict-directed heuristics, ICTAI'04]. These series are denoted by ehi-85 and ehi-90. ehi-85 100 2 all unsat EXT
ehi-90 100 2 all unsat EXT
Geom The Geometric problem has been proposed by Rick Wallace. The geometric instances are a kind of random instances generated as follows. Instead of a density parameter, a "distance" parameter, dst, is used such that dst <= sqrt(2). For each variable, two coordinates are chosen at random so the associated point lies in the unit square. Then for each variable pair, (x,y), if the distance between their associated points is less than or equal to dst, the arc (x,y) is added to the constraint graph. Constraint relations are created in the same way as they are for homogeneous random CSP instances. Each instance is prefixed by geom. geom 100 2 92 sat
8 unsat 		EXT
Lard The Lard instances are all random ``large'' binary instances. The constraint graphs are complete. Instance lard-n has n variables and domain size n. The constraints allow for any assignment of the first n/2 values to any variable, which makes these instances trivially satisfiable. This series of 10 instances has been proposed by Marc Van Dongen for the 2006 CSP Solver Competition. lard 10 2 all sat EXT

RAND (Random instances)

Problem Series #Instances Arity Satisfiability Type
Marc This is the contestant series submitted by Marc van Dongen to the 2005 competition. marc 10 2 5 sat
5 unsat		 EXT
Model B 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-23 10 2 5 sat
5 unsat 		EXT
rand-2-24 10 2 3 sat
7 unsat 		EXT
rand-2-25 10 2 6 sat
4 unsat 		EXT
rand-2-26 10 2 5 sat
5 unsat 		EXT
rand-2-27 10 2   EXT
Model D Here are seven series of 100 binary random instances (generated following Model D) situated at the phase transition of search. For each class <n,d,e,t>, 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,8,753,0.1> 100 2 51 sat
49 unsat		 EXT
<40,11,414,0.2> 100 2 53 sat
47 unsat		 EXT
<40,16,250,0.35> 100 2 48 sat
52 unsat		 EXT
<40,25,180,0.5> 100 2 50 sat
50 unsat		 EXT
<40,40,135,0.65> 100 2 52 sat
48 unsat		 EXT
<40,80,103,0.8> 100 2 47 sat
53 unsat		 EXT
<40,180,84,0.9> 100 2 47 sat
53 unsat		 EXT
Model RB 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. 		frb30-15 5*2 2 all sat EXT
frb35-17 5*2 2 all sat EXT
frb40-19 5*2 2 all sat EXT
frb45-21 5*2 2 all sat EXT
frb50-23 5*2 2 all sat EXT
frb53-24 5*2 2 all sat EXT
frb56-25 5*2 2 all sat EXT
frb59-26 5*2 2 all sat EXT
Model RB 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 50 2 29 sat
21 unsat		 EXT
2-30-15 forced 50 2 all sat EXT
2-40-19 50 2 20 sat
30 unsat		 EXT
2-40-19 forced 50 2 all sat EXT
2-50-23 50 2   EXT
2-50-23 forced 50 2 all sat EXT
3-20-20 50 3 25 sat
25 unsat		 EXT
3-20-20 forced 50 3 all sat EXT
3-24-24 50 3   EXT
3-24-24 forced 50 3 all sat EXT
3-28-28 50 3   EXT
3-28-28 forced 50 3 all sat EXT
Positive Table Constraints These are four series of non binary instances involving positive table constraints. Some of them have been given to illustrate [Lecoutre-Szymanek, Generalized Arc Consistency for Positive Table Constraints, CP'06]. rand-8-20-5 20 8 all sat EXT
rand-10-20-10 20 10 all unsat EXT
rand-10-60-20 50 10 all unsat EXT
rand-5-12-12 50 5 all unsat EXT

BOOL (Boolean instances)

Problem Series #Instances Arity Satisfiability Type
Dimacs aim-50 24 3 16 sat
8 unsat		 EXT
aim-100 24 3 16 sat
8 unsat		 EXT
aim-200 24 3   EXT
dubois 13 3   EXT
jnhSat 16 > 2 all sat EXT
jnhUnsat 34 > 2 all unsat EXT
pret 8 3   EXT
ssa 8 > 2   EXT
varDimacs 9 > 2   EXT
Pseudo-Boolean instances Here are 21 series of non binary instances. The last one has been recently generated and involve the global constraint weightedSum.. 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:
The web pages of Fadi A. Aloul
The web pages of Niklas Eén
The web pages of Vasco Manquinho
The web pages of Joachim Paul Walser
UCLID: A Verification Tool for Infinite-State Systems
MIPLIB - Mixed Integer Problem Library 		aim 48 >2 all sat INT
chnl 21 >2   INT
circuits 7 >2 all sat INT
course 4 >2   INT
fpga 36 >2   INT
garden 7 >2 all sat INT
ii 41 >2 all sat INT
jnh 16 >2 all sat INT
logic-synthesis 17 >2 all sat INT
mps 49 >2   INT
mpsReduced 106 >2   INT
niklas 19 >2   INT
par 30 >2   INT
ppp 6 >2   INT
primesDimacs 11 >2   INT
radar 12 >2 all sat INT
routing 15 >2   INT
ssa 8 >2 4 sat
4 unsat 		INT
ttp 8 >2   INT
uclid 39 >2   INT
pseudoGLB 384 >2   GLB

Max-CSP

Important: there is no difference in term of representation between a CSP instance and a Max-CSP instance. Simply, the instances posted below are easy for satisfaction (determining if it is possible to find a full assignment that does not violate any constraint) but hard for optimization (determining what is the maximum number of constraints that can be satisfied).
Problem Series #Instances Arity Satisfiability Type
Max-CSP
RLFAP All these instances have been generated by converting the wcsp instances located here . They are mainly interesting for Max-CSP (as most of them are quite easy for satisfaction). It is important to remark that information about weights/costs has been lost due to the translation wcsp/csp. However, we believe that the structure has been preserved, and so, such instances certainly remain interesting to study max-CSP solvers. Of course, for original instances (weighted CSP instances), just consult Soft CSP Benchmarks . Thank you to Simon de Givry for his help. 		graphs 6 2 all unsat EXT
scens 13 2 all unsat EXT
subs6 7 2 all unsat EXT
subs7 7 2 all unsat EXT
Max-CSP
spot5 All these instances have been generated by converting the wcsp instances located here . They are mainly interesting for Max-CSP (as most of them are quite easy for satisfaction). It is important to remark that information about weights/costs has been lost due to the translation wcsp/csp. However, we believe that the structure has been preserved, and so, such instances certainly remain interesting to study max-CSP solvers. Of course, for original instances (weighted CSP instances), just consult Soft CSP Benchmarks . Thank you to Simon de Givry for his help. 		spot5 21 3 all unsat EXT
Max-CSP
planning All these instances have been generated by converting the wcsp instances located here . They are mainly interesting for Max-CSP (as most of them are quite easy for satisfaction). It is important to remark that information about weights/costs has been lost due to the translation wcsp/csp. However, we believe that the structure has been preserved, and so, such instances certainly remain interesting to study max-CSP solvers. Of course, for original instances (weighted CSP instances), just consult Soft CSP Benchmarks . Thank you to Simon de Givry for his help. 		planning 71 2 all unsat EXT
Max-CSP
warehouses		 warehouses 57 2 all unsat EXT
Max-CSP
maxclique		 maxclique 63 2 all unsat EXT
Max-CSP
pedigree		 pedigree 14 2 all unsat EXT
Max-CSP
maxcut		 maxcut-30 100 2 all unsat EXT
maxcut-40 100 2 all unsat EXT
maxcut-50 100 2 all unsat EXT
maxcut-50 100 2 all unsat EXT
Max-CSP
cnf		 cnf-2-40-100-1000 100 2 all unsat EXT
cnf-2-40-1100-2000 100 2 all unsat EXT
cnf-2-40-2100-3000 100 2 all unsat EXT
cnf-2-80-100-1000 100 2 8 sat
92 unsat		 EXT
cnf-2-80-1100-2000 100 2 all unsat EXT
cnf-3-40-100-1000 100 2 12 sat
88 unsat		 EXT
cnf-3-40-1100-2000 100 2 all unsat EXT
cnf-3-40-2100-3000 100 2 all unsat EXT
cnf-3-80-100-1000 100 2 30 sat
70 unsat		 EXT
cnf-3-80-1100-2000 100 2 all unsat EXT
Max-CSP
kbtree		 kbtree-5-2-4-5 450 2 150 sat
300 unsat		 EXT
kbtree-9-2-3-5 450 2 150 sat
300 unsat		 EXT
kbtree-9-5-3-5 450 2 56 sat
394 unsat		 EXT
kbtree-9-7-3-5 450 2 55 sat
395 unsat		 EXT
Max-CSP
random		 completeLoose 50 2 all unsat EXT
completeTight 50 2 all unsat EXT
denseLoose 50 2 all unsat EXT
denseTight 50 2 all unsat EXT
sparseLoose 90 2 all unsat EXT
sparseTight 50 2 all unsat EXT
Pi These 5 series have been generated by Rick Wallace in the context of the 2006 CSP Solver Competition. All instances are random but embed a little structure. For pi-X-Y-Z-tT, X is the number of variables, Y is the domain size, Z is the density - in terms of edges added to a spanning tree, and T is the tightness of a constraint (fixed tightness). For instances involving 20 and 30 variables, two sets were generated. The ones with lower tightness have optimal distances of about 2, the ones with higher tightness have distances around 6-7 (20 variables) or 9 (30 variables). The instances involving 40 variables have distances of about 2. pi-20-10-20-t60 100 2   EXT
pi-20-10-20-t70 100 2   EXT
pi-30-10-25-t48 100 2   EXT
pi-30-10-25-t58 100 2   EXT
pi-40-10-08-t60 100 2   EXT

WCSP

All these instances come from here, and have been translated in format XCSP 2.1. Of course, for original instances (in format .wcsp), just consult Soft CSP Benchmarks . Thank you to Simon de Givry for his help.
Problem Series #Instances Arity Satisfiability Type
Academics Some academics instances. academics 15     EXT
Dimacs dimacs 25     EXT
Graph coloring These instances have been produced from the clique part of the DIMACS Challenge (Trick, 2002). The objective is to minimize the number of violated disequality constraints (unsatisfiable instances). coloring 22 2   EXT
Jnh jnh 44     EXT
Pedigree pedigree 19     EXT
Planning Problems from planning in temporal and metric domains. They have been translated from Planning ICAPS Competitions by (Cussat-Blanc and Régnier, 2006). bwt 10     EXT
depot 4     EXT
driver 22     EXT
logistics 4     EXT
mprime 12     EXT
rover 4     EXT
satellite 7     EXT
zenotravel 8     EXT
RLFAP Instances from the radio link frequency assignment problem. graphs 10     EXT
scens 21     EXT
celar 15     EXT
Spot5 These are instances of an earth observation daily management problem. They have been produced by CNES (French Space Agency), Toulouse, France, 1996, using a simulator of the future order book of the satellite SPOT5. Note that instances number 1401-1506 have a memory limitation (global constraint) which is ignored here. spot5 21     EXT
Warehouse These are instances from the warehouse location problem. They correspond to randomly generated instances by (Kratica et al, 2001), except capa, capb, and capc from ORLIB. warehouse 55 2   EXT