### XCSP3 is born!

XCSP3 is a XML-based format designed to represent combinatorial constrained problems. It is compact, easy to read and to parse. Importantly, this new format (partly) captures the structure of the problem models, through the possibilities of declaring arrays of variables, and identifying syntactic and semantic groups of constraints. XCSP3 introduces a limited set of basic constraint forms, and allows many variations of them through lifting, restriction, sliding, logical combination and relaxation mechanisms. As a result, XCSP3 encompasses practically all constraints that can be found in major constraint solvers.

The objective of XCSP3 is to ease the effort required to test and compare different algorithms by providing a common test-bed of combinatorial constrained instances.

### Quick, have a look at XCSP3 on www.xcsp.org

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

- CSP instances
- Weighted CSP (WCSP) instances
- Quantified CSP (QCSP) instances

- constraints defined in extension
- constraints defined in intension
- global constraints

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.

The 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:

- two constraints defined on the same scope (for example, the instance fapp01-0200-0).
- several constraints that share the same scope under permutations (for example, see constraints C0 and C13 in langford-2-4-ext).
- empty relations (for example, the instance bqwh-15-106-0_ext).
- unary constraints (for example, the instance zebra).
- the following instances: queens-12 and queens-12-ext. Do you find 14200 solutions?
- the following instances: crossword-m1-debug-05-01 and crossword-m1-debug-05-02. Do you find 48 solutions?

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

- we try to limit the length of any file name to 30 characters (it renders easier the task of referencing instances in tables, charts, etc.).
- we just use alphanumeric characters as well as characters '-' and '_' (and so, we do not use the exotic characters '?', '!', ',' etc. or even white spaces).
- we put the identification of the problem (in abbreviation, if necessary) at the beginning of the file name.
- the character "-" is used as a separator of parameter values. If any, the random seed value is the last given parameter value.
- the character "_" is used to introduce (a) token(s) that allow(s) to identify some general feature(s). For example, when an instance only involves constraints in extension, one can use "_ext". These tokens are given after the parameter values (if any).

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

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:

- REAL: instances from real world applications,
- PATT: instances following a regular pattern and involving a random generation,
- ACAD: instances from the academia and which do not involve any random generation,
- QRND: random instances containing a small structure,
- RAND: pure random instances.

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:

- BOOL: instances only involving Boolean variables.

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:

- EXT: all constraints are defined in extension,
- INT: at least one constraint is defined in intension, and potentially some constraints can be defined in extension,
- GLB: at leats one constraint refers to a global constraint, and potentially some constraints can be defnied in extension or/and in intension.

- Max-CSP: the problem of determining the maximum number of constraints that can be satisfied

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

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 |