http://www.xs4all.nl/~bcraenen/RepositoryCsp
Dr. B.G.W. Craenen <bcraenen@xs4all.nl>
“RepositoryCsp”

RepositoryCsp provides a repository of randomly generated constraint satisfaction problems (CSPs), generated by JavaCsp. I created RepositoryCsp mostly because I needed a benchmark testset for the PhD research in CSPs and although some random CSP generators have been placed on Internet for use, finding a static testset for comparison use is difficult. I hope that making a such a testset available will encourage direct comparison of results.

RepositoryCsp includes two CSP testsets. One with 10 variables and a domain size of 10 elements and one with 30 variables and a domain size of 5 elements. Both density (connectivity) and tightness of the instances ranges from 0.1 to 0.9 with a 0.1 interval, for a total of 81 permutations. I have generated a basic complement of 25 instances, all of which are checked if there is a solution.

CSP(10,10) complete testset

csps_10_10.zip

list_10_10

The zip-file contains the whole testset, including unsolvable instances, the list-file is a list of all included instances.

CSP(10,10) solvable testset

csps_10_10_solvable.zip

list_10_10_solvable

The zip-file contains a testset with only solvable instances, the list-file is a list of all included instances.

CSP(10,10) testset details

The following table notes the number of solvable instances (first number) and the number of unsolvable instances (second number):

t=0.1t=0.2t=0.3t=0.4t=0.5t=0.6t=0.7t=0.8t=0.9
d=0.1 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 23 - 2
d=0.2 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 4 - 21
d=0.3 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 4 - 21 0 - 25
d=0.4 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 7 - 18 0 - 25 0 - 25
d=0.5 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 18 - 7 0 - 25 0 - 25 0 - 25
d=0.6 25 - 0 25 - 0 25 - 0 25 - 0 25 - 0 2 - 23 0 - 25 0 - 25 0 - 25
d=0.7 25 - 0 25 - 0 25 - 0 25 - 0 14 - 11 0 - 25 0 - 25 0 - 25 0 - 25
d=0.8 25 - 0 25 - 0 25 - 0 25 - 0 2 - 23 0 - 25 0 - 25 0 - 25 0 - 25
d=0.9 25 - 0 25 - 0 25 - 0 20 - 5 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25

All instances have been checked if they have a solution. In the next table you will find the average number of conflict checks needed by a forward checking with conflict directed backjumping algorithm. In parenthesis the standard deviation is given:

t=0.1t=0.2t=0.3t=0.4t=0.5t=0.6t=0.7t=0.8t=0.9
d=0.1437.76
(9.0934)
424.08
(13.555)
408.92
(19.406)
401
(19.585)
393.04
(24.431)
376.56
(33.823)
393.04
(50.188)
603.40
(1036.6)
858.56
(1292.2)
d=0.2425.12
(10.978)
404.12
(16.925)
374.92
(22.712)
368.60
(24.307)
349.36
(27.515)
367.48
(103.93)
545.88
(313.51)
1218.4
(1012.4)
7658.8
(21542)
d=0.3409.48
(12.794)
381.60
(12.416)
351.36
(24.515)
334.68
(27.763)
373.88
(91.918)
719.64
(664.25)
3879.0
(6084.3)
11617
(23016)
2632.2
(4104.5)
d=0.4403.40
(12.897)
371.56
(14.543)
329.60
(17.161)
320.24
(39.117)
429.92
(238.62)
1499.7
(2817.3)
7695.2
(6129.6)
2967.8
(2692.6)
1454.6
(1887.8)
d=0.5390.60
(18.099)
345.56
(20.040)
326.32
(52.268)
387
(284.12)
1138
(1884.7)
8026.9
(6847.0)
4568.1
(3583.5)
1383.6
(813.91)
691.32
(825.79)
d=0.6381.80
(13.772)
332.52
(13.696)
304.92
(36.658)
406.88
(227.74)
2824.9
(2913.2)
8671.3
(6186.3)
3225.8
(1352.7)
1269.9
(687.85)
526.64
(280.82)
d=0.7374.80
(15.911)
318.80
(14.532)
303.76
(41.498)
767.92
(559.87)
9967.0
(7980.2)
3896.7
(1645.1)
1899.5
(838.62)
850.12
(441.62)
405
(171.86)
d=0.8369.56
(14.709)
305.24
(21.936)
315.08
(67.640)
2283
(4627.9)
7131.2
(3568.1)
2709.4
(1017.8)
1600.5
(606.36)
727.72
(143.32)
353.08
(105.65)
d=0.9361.56
(16.140)
290.72
(19.531)
381.64
(206.10)
5893.9
(5601.6)
4534.8
(1425.5)
2244.5
(616.25)
1092.4
(166.17)
684.16
(98.705)
277.24
(98.757)
CSP(30,5) complete testset

csps_30_05.zip

list_30_05

The zip-file contains the whole testset, including unsolvable instances, the list-file is a list of all included instances.

CSP(30,5) solvable testset

csps_30_05_solvable.zip

list_30_05_solvable

The zip-file contains a testset with only solvable instances, the list-file is a list of all included instances.

CSP(30,5) testset details

The following table notes the number of solvable instances (first number) and the number of unsolvable instances (second number):

t=0.1t=0.2t=0.3t=0.4t=0.5t=0.6t=0.7t=0.8t=0.9
d=0.1 25 - 0 25 - 0 25 - 0 25 - 0 17 - 8 0 - 25 0 - 25 0 - 25 0 - 25
d=0.2 25 - 0 25 - 0 25 - 0 2 - 23 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25
d=0.3 25 - 0 25 - 0 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25
d=0.4 25 - 0 25 - 0 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25
d=0.5 25 - 0 1 - 24 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25
d=0.6 25 - 0 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25
d=0.7 25 - 0 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25
d=0.8 25 - 0 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25
d=0.9 21 - 4 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25 0 - 25

All instances have been checked if they have a solution. In the next table you will find the average number of conflict checks needed by a forward checking with conflict directed backjumping algorithm. In parenthesis the standard deviation is given:

t=0.1t=0.2t=0.3t=0.4t=0.5t=0.6t=0.7t=0.8t=0.9
d=0.1 1963.8
(50.388)
1825.7
(83.372)
2124.4
(602.54)
5286.6
(7038.7)
341940
(927030)
69267
(72648)
9237.5
(11777)
1542.6
(116.5)
725.08
(1017.2)
d=0.2 1823.6
(53.513)
2249.1
(1065.1)
98028
(190260)
446410
(522270)
22128
(25155)
4101.5
(5539.2)
1030.4
(640.41)
532.04
(309.61)
253.36
(177.66)
d=0.3 1703.6
(107.40)
22670
(49758)
524220
(586020)
34654
(30618)
5527.8
(4832.3)
1370.2
(1390.4)
602.48
(251.49)
229.32
(124.84)
133.68
(87.87)
d=0.4 1805.0
(424.06)
676030
(990850)
75108
(50274)
10241
(5732.6)
2004.0
(1024.9)
893.12
(494.10)
414.16
(266.76)
192.72
(129.61)
111.80
(54.427)
d=0.5 1829.6
(587.31)
661260
(552400)
18608
(10681)
4162.2
(1824.1)
1239.4
(397.42)
727.04
(377.96)
317.52
(153.20)
141.00
(83.417)
69.600
(38.835)
d=0.6 7264.1
(8959.8)
162760
(102890)
11186
(6175.7)
2694.2
(1016.2)
1096.2
(509.05)
485.28
(167.52)
215.76
(90.671)
114.40
(35.069)
85.600
(45.628)
d=0.7 69144
(98067)
61816
(37468)
5882.0
(2792.7)
1721.8
(415.84)
798.16
(308.55)
370.16
(143.41)
185.56
(88.623)
109.00
(49.011)
65.400
(34.397)
d=0.8 228800
(409360)
36389
(16056)
4004.9
(1130.7)
1236.5
(364.85)
710.48
(144.64)
351.84
(120.97)
179.80
(72.563)
89.200
(36.620)
60.200
(20.690)
d=0.9 1675000
(1874700)
16672
(5865.8)
2717.3
(670.47)
1160.6
(295.48)
515.96
(139.56)
309.16
(108.64)
135.60
(50.854)
80.400
(28.097)
48.200
(14.207)
copyright © B.G.W. Craenen