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.
The zip-file contains the whole testset, including unsolvable instances, the list-file is a list of all included instances.
The zip-file contains a testset with only solvable instances, the list-file is a list of all included instances.
The following table notes the number of solvable instances (first number) and the number of unsolvable instances (second number):
| t=0.1 | t=0.2 | t=0.3 | t=0.4 | t=0.5 | t=0.6 | t=0.7 | t=0.8 | t=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.1 | t=0.2 | t=0.3 | t=0.4 | t=0.5 | t=0.6 | t=0.7 | t=0.8 | t=0.9 | |
|---|---|---|---|---|---|---|---|---|---|
| d=0.1 | 437.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.2 | 425.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.3 | 409.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.4 | 403.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.5 | 390.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.6 | 381.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.7 | 374.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.8 | 369.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.9 | 361.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) |
The zip-file contains the whole testset, including unsolvable instances, the list-file is a list of all included instances.
The zip-file contains a testset with only solvable instances, the list-file is a list of all included instances.
The following table notes the number of solvable instances (first number) and the number of unsolvable instances (second number):
| t=0.1 | t=0.2 | t=0.3 | t=0.4 | t=0.5 | t=0.6 | t=0.7 | t=0.8 | t=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.1 | t=0.2 | t=0.3 | t=0.4 | t=0.5 | t=0.6 | t=0.7 | t=0.8 | t=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) |