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