You are here

Positive Table Constraints Benchmarks

Benchmarks problems defined using only positive table constraints. The folder contains 14 different benchmarks.

  • Crosswords_lexVg, Crosswords_ogdVg, Crosswords_ukVg and Crosswords_wordsVg: Instances of the crosswords problem. This is the problem of filling a predefined grid with words from a dictionary. Those instance sets come from here. The instances in those sets differ by the dictionary they use to get the words from. The grids are all the same and empty. Inside a set, different grid sizes are used, varying the arity of the table constraints. The instance set lexVg is using the dictionary defined in [Samaras-Stergiou, Binary encodings of non binary satisfaction problems: algorithms and experimental results, JAIR, 2005]. Instances in ogdVg use a french dictionary. The set ukVg is using the UK cryptic solvers dictionary. The last instance set, wordsVg, uses the dictionary in /usr/dict/words under Linux. The dictionaries of lexVg and wordsVg instances sets have a rather small dictionary, leading to small tables. On the contrary, ogdVg and ukVg have large dictionaries. As, for those problems, the same word can be used multiple times, only table constraints are used to encode the problem.
  • geom: Instances of the geometric problem are random instances generated following a specific structure proposed by Rick Wallace. Each variable is randomly placed in the unit square. A fixed distance (less than 2) is randomly chosen. For each pair of variables (x, y), if the distance between their associated points is less than or equal to this fixed distance, the arc (x, y) is added to the constraint graph. Constraint relations are then created as they are in fully random CSP instances. The constraints of this problem are thus binary. This instance set comes from here and counts 100 instances.
  • k5_n10_d10_m15_p08: These instances contain random table constraints of random scope generated by the RD-model [Xu K, Boussemart F, Hemery F, Lecoutre C Random constraint satisfaction: Easy generation of hard (satisfiable) instances, AI, 2007]. Parameters are chosen to generate instances close to the phase transition, using Theorems 1 and 2 from the paper. The instances have 10 variables, a uniform domain size of 10, and 15 table constraints of arity 5. The expected number of tuples in each table is thus 20000. This instance set counts 10 instances.
  • langford2, langford3 and langford4: Langford number problem L(k,n) amounts to arranging k sets of numbers 1 to n into a sequence of numbers, so that each occurrence of a number m is m numbers apart from its previous occurrence. This is problem 24 of CSPLIB. Those problems can be modeled with binary positive table constraints only. The set langfordk contains langford problems L(k,n) for various n. Those instances come from here.
  • modRenault: The modified renault problem instances originate from a Renault Megane configuration problem. This problem has been modified in order to generate a series of instances. Those instances have the particularity to present large tables (up to 50 k tuples) of large arities (up to arity 10). Those instances come from here.
  • s20_p03_c20_d10_n10_l5: This instance set contains 100 instances composed of random regular constraints in positive table constraint form. The Regular constraint [Pesant G. A Regular Language Membership Constraint for Finite Sequences of Variables. CP 2004] is a global constraint on a sequence of variable stating that the values taken by the variables have to form a word in a given regular language. The regular language is specified by a deterministic finite automaton. The regular constraints can be encoded efficiently with table constraints [Quimper C.G., Walsh T. Global Grammar Constraints. CP 2006]. The instances in this set contain 20 regular constraints on 10 different variables. Each regular constraint has a scope of 5 variables, chosen randomly. The domains of the variable is of size 10. Each regular constraint is 20 states and has a randomly created transition table. Amongst the states, 30 % of them are randomly chosen to be final. The parameters were chosen to produce instances with a significant number of fails and choice points. The regular constraints are transformed into ternary table constraints.
  • TSP_20, TSP_25: Each of those sets contains 15 instances of the Traveling Salesman Problem (TSP) constraint satisfaction problem. The number in the set name refers to the number of cities. Those sets were taken from here. They have been generated by R. Szymanek for the 2005 solver competition. The negative table constraints found in those instances have been transformed into positive ones.
  • TSP_Quat_20: Each instance of this set is a transformation of its corresponding instance in the set TSP_20. The binary table constraints without variables in common are merged 2 by 2 into arity 4 table constraints.
AttachmentSize
All Instances Table Constraints45.24 MB
Crosswords LexVg806.35 KB
Crosswords OgdVg13.36 MB
Crosswords UkVg7.61 MB
Crosswords WordsVg1.4 MB
Geom2.79 MB
k5_n10_d10_m15_p085.63 MB
Langford283.57 KB
Langford3152.37 KB
Langford4230.87 KB
ModRenault10.06 MB
s20_p03_c20_d10_n10_l51.29 MB
TSP_20380.57 KB
TSP_25415.04 KB
TSP_Quat_201.05 MB