Zhang-Hua Fu and Jin-Kao Hao. "Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget and Hop Constraints". Last updated: 15/04/2014
Group G1: Click here to download the results obtained by memetic for all the 144 instances of group G1
Group G2: Click here to download the results obtained by memetic for all the 60 instances of group G2
Group G3: Click here to download the results obtained by memetic for all the 124 instances of group G3
Group G4: The best known results of this group are provided respectively in Table 1 (upper bound indicates the sum of the profits of all the reachable profitable vertices). Specifically, all the results obtained by memetic with M=50 on this group could be download from here
Table 1. Results obtained by Memetic(M=500) with respect to ILS and Memetic/DP in the above paper, corresponding to the 56 most challenging instances of group G4 with unknown optimal results (the output files of the best results are attached finally).
No. | Graph | b | h | Upper Bound | ILS | Memetic/DP | Memetic | Best Results(All) |
1 | steinc8_10 | 20 | 5 | 301 | 230 | 230 | 230 | Click here |
2 | steinc8_10 | 50 | 5 | 301 | 116 | 116 | 116 | Click here |
3 | steinc8_10 | 20 | 15 | 439 | 327 | 328 | 330 | Click here |
4 | steinc8_10 | 50 | 15 | 439 | 168 | 171 | 171 | Click here |
5 | steinc8_10 | 20 | 25 | 439 | 330 | 331 | 330 | Click here |
6 | steinc8_10 | 50 | 25 | 439 | 172 | 172 | 172 | Click here |
7 | steinc8_100 | 20 | 5 | 3073 | 2373 | 2380 | 2380 | Click here |
8 | steinc8_100 | 50 | 5 | 3073 | 1216 | 1216 | 1216 | Click here |
9 | steinc8_100 | 20 | 15 | 4463 | 3414 | 3412 | 3418 | Click here |
10 | steinc8_100 | 50 | 15 | 4463 | 1764 | 1774 | 1774 | Click here |
11 | steinc8_100 | 20 | 25 | 4463 | 3414 | 3429 | 3443 | Click here |
12 | steinc8_100 | 50 | 25 | 4463 | 1792 | 1792 | 1792 | Click here |
13 | steinc9_10 | 20 | 5 | 607 | 301 | 301 | 302 | Click here |
14 | steinc9_10 | 50 | 5 | 607 | 149 | 149 | 149 | Click here |
15 | steinc9_10 | 20 | 15 | 648 | 377 | 374 | 376 | Click here |
16 | steinc9_10 | 50 | 15 | 648 | 184 | 184 | 183 | Click here |
17 | steinc9_10 | 20 | 25 | 648 | 379 | 380 | 377 | Click here |
18 | steinc9_10 | 50 | 25 | 648 | 186 | 186 | 186 | Click here |
19 | steinc9_100 | 20 | 5 | 6142 | 3112 | 3112 | 3112 | Click here |
20 | steinc9_100 | 50 | 5 | 6142 | 1563 | 1563 | 1563 | Click here |
21 | steinc9_100 | 20 | 15 | 6566 | 3918 | 3875 | 3873 | Click here |
22 | steinc9_100 | 50 | 15 | 6566 | 1888 | 1899 | 1879 | Click here |
23 | steinc9_100 | 20 | 25 | 6566 | 3932 | 3912 | 3906 | Click here |
24 | steinc9_100 | 50 | 25 | 6566 | 1895 | 1918 | 1909 | Click here |
25 | steinc10_10 | 20 | 5 | 886 | 386 | 388 | 388 | Click here |
26 | steinc10_10 | 50 | 5 | 886 | 184 | 185 | 185 | Click here |
27 | steinc10_10 | 20 | 15 | 1248 | 545 | 551 | 553 | Click here |
28 | steinc10_10 | 50 | 15 | 1248 | 247 | 247 | 247 | Click here |
29 | steinc10_10 | 20 | 25 | 1248 | 553 | 558 | 561 | Click here |
30 | steinc10_10 | 50 | 25 | 1248 | 251 | 256 | 254 | Click here |
31 | steinc10_100 | 20 | 5 | 8929 | 4079 | 4088 | 4069 | Click here |
32 | steinc10_100 | 50 | 5 | 8929 | 1939 | 1940 | 1940 | Click here |
33 | steinc10_100 | 20 | 15 | 12533 | 5662 | 5682 | 5686 | Click here |
34 | steinc10_100 | 50 | 15 | 12533 | 2550 | 2566 | 2601 | Click here |
35 | steinc10_100 | 20 | 25 | 12533 | 5743 | 5838 | 5773 | Click here |
36 | steinc10_100 | 50 | 25 | 12533 | 2587 | 2586 | 2632 | Click here |
37 | steinc13_10 | 100 | 5 | 439 | 252 | 254 | 253 | Click here |
38 | steinc13_10 | 100 | 15 | 439 | 313 | 312 | 316 | Click here |
39 | steinc13_10 | 100 | 25 | 439 | 313 | 314 | 314 | Click here |
40 | steinc13_100 | 100 | 5 | 4463 | 2609 | 2609 | 2622 | Click here |
41 | steinc13_100 | 100 | 15 | 4463 | 3243 | 3253 | 3255 | Click here |
42 | steinc13_100 | 100 | 25 | 4463 | 3260 | 3257 | 3260 | Click here |
43 | steinc14_10 | 100 | 5 | 648 | 368 | 368 | 370 | Click here |
44 | steinc14_10 | 100 | 15 | 648 | 396 | 396 | 398 | Click here |
45 | steinc14_10 | 100 | 25 | 648 | 393 | 396 | 397 | Click here |
46 | steinc14_100 | 100 | 5 | 6566 | 3811 | 3843 | 3847 | Click here |
47 | steinc14_100 | 100 | 15 | 6566 | 4151 | 4156 | 4172 | Click here |
48 | steinc14_100 | 100 | 25 | 6566 | 4136 | 4161 | 4150 | Click here |
49 | steinc15_10 | 20 | 5 | 1248 | 1210 | 1218 | 1221 | Click here |
50 | steinc15_10 | 100 | 5 | 1248 | 457 | 458 | 462 | Click here |
51 | steinc15_10 | 100 | 15 | 1248 | 559 | 559 | 558 | Click here |
52 | steinc15_10 | 100 | 25 | 1248 | 558 | 558 | 558 | Click here |
53 | steinc15_100 | 20 | 5 | 12533 | 12266 | 12370 | 12392 | Click here |
54 | steinc15_100 | 100 | 5 | 12533 | 4741 | 4779 | 4807 | Click here |
55 | steinc15_100 | 100 | 15 | 12533 | 5792 | 5807 | 5807 | Click here |
56 | steinc15_100 | 100 | 25 | 12533 | 5792 | 5807 | 5822 | Click here |
Group G5: The results of this group are provided respectively in Table 2.
Table 2. Results obtained by memetic (M=500) in the above paper, with respect to our previous BLS algorithm, corresponding to the 30 newly generated instances of group G5 (the output files of the best results are attached finally).
No. | Graph | b | h | Upper Bound | BLS | Memetic | Best Results(All) |
1 | steinc16_10 | 10000 | 5 | 27 | 19 | 19 | Click here |
2 | steinc16_10 | 10000 | 15 | 27 | 19 | 19 | Click here |
3 | steinc16_10 | 10000 | 25 | 27 | 19 | 19 | Click here |
4 | steinc16_100 | 10000 | 5 | 274 | 203 | 203 | Click here |
5 | steinc16_100 | 10000 | 15 | 274 | 203 | 203 | Click here |
6 | steinc16_100 | 10000 | 25 | 274 | 203 | 203 | Click here |
7 | steinc17_10 | 5000 | 5 | 59 | 47 | 47 | Click here |
8 | steinc17_10 | 5000 | 15 | 59 | 50 | 50 | Click here |
9 | steinc17_10 | 5000 | 25 | 59 | 50 | 50 | Click here |
10 | steinc17_100 | 5000 | 5 | 604 | 481 | 481 | Click here |
11 | steinc17_100 | 5000 | 15 | 604 | 513 | 513 | Click here |
12 | steinc17_100 | 5000 | 25 | 604 | 513 | 513 | Click here |
13 | steinc18_10 | 1000 | 5 | 439 | 311 | 312 | Click here |
14 | steinc18_10 | 1000 | 15 | 439 | 334 | 338 | Click here |
15 | steinc18_10 | 1000 | 25 | 439 | 334 | 338 | Click here |
16 | steinc18_100 | 1000 | 5 | 4463 | 3245 | 3252 | Click here |
17 | steinc18_100 | 1000 | 15 | 4463 | 3478 | 3526 | Click here |
18 | steinc18_100 | 1000 | 25 | 4463 | 3506 | 3526 | Click here |
19 | steinc19_10 | 1000 | 5 | 648 | 390 | 392 | Click here |
20 | steinc19_10 | 1000 | 15 | 648 | 412 | 417 | Click here |
21 | steinc19_10 | 1000 | 25 | 648 | 407 | 418 | Click here |
22 | steinc19_100 | 1000 | 5 | 6566 | 4021 | 4080 | Click here |
23 | steinc19_100 | 1000 | 15 | 6566 | 4265 | 4355 | Click here |
24 | steinc19_100 | 1000 | 25 | 6566 | 4265 | 4337 | Click here |
25 | steinc20_10 | 1000 | 5 | 1248 | 441 | 436 | Click here |
26 | steinc20_10 | 1000 | 15 | 1248 | 486 | 479 | Click here |
27 | steinc20_10 | 1000 | 25 | 1248 | 487 | 481 | Click here |
28 | steinc20_100 | 1000 | 5 | 12533 | 4527 | 4565 | Click here |
29 | steinc20_100 | 1000 | 15 | 12533 | 5124 | 5019 | Click here |
30 | steinc20_100 | 1000 | 25 | 12533 | 5045 | 5054 | Click here |
Notes:
1. All the STPRBH graphs used in the paper (18 ones corresponding to series B and 40 ones corresponding to series C) can be downloaded from here, or can be provided on request to fu@info.univ-angers.fr or fuzhanghua1984@163.com. Note that these graphs for STPRBH are adapted by Costa et al., based on the initial Steiner graphs from OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/orlib/steininfo.html. For each test graph,the root vertex is chosen as the profitable vertex (with ri>0) with the smallest index. Since vertex 1 is not always a profitable vertex, it is not always the root vertex. For convenience, in our implementation of Memetic algorithm, if vertex 1 is not the root vertex, we swap it with the profitable vertex with the smallest index. Therefore, in the solutions reported by our Memetic algorithm, vertex 1 is always the root vertex.
2. The format of the solution file is as follows:
First row: the number of edges existing in the solution
Then, for each edge:(begin vertex, end vertex)
Finally followed by:
Total revenues (sum revenues of all the profitable vertices in the test graph)
Total edge cost (sum cost of all the edges in the test graph )
Allowed budget(the constraint)
Revenues collected by our Memetic algorithm
Consumed budget