Zhanghua Fu and Jin-Kao Hao. "Breakout Local Search for the Steiner Tree Problem with Revenue, Budget and Hop Constraints". European Journal of Operational Research 232(1): 209-220, 2014 (The source code of our program is available here).

Table1. Results obtained by BLS (Single-BLS and Multiple-BLS, respectively) in the above paper, corresponding to the first group of 60 instances, which have all been solved to optimality by previous exact algorithms. 

No. Graph b h Opt Single-BLS Multiple-BLS Results(AllC1)
1 steinc1_10 10 5 8 8 8 Click here
2 steinc1_10 30 5 8 8 8 Click here
3 steinc1_10 10 15 27 27 27 Click here
4 steinc1_10 30 15 27 27 27 Click here
5 steinc1_10 10 25 27 27 27 Click here
6 steinc1_10 30 25 27 27 27 Click here
7 steinc1_100 10 5 71 71 71 Click here
8 steinc1_100 30 5 71 71 71 Click here
9 steinc1_100 10 15 274 274 274 Click here
10 steinc1_100 30 15 274 274 274 Click here
11 steinc1_100 10 25 274 274 274 Click here
12 steinc1_100 30 25 274 274 274 Click here
13 steinc2_10 10 5 32 32 32 Click here
14 steinc2_10 30 5 32 32 32 Click here
15 steinc2_10 10 15 59 59 59 Click here
16 steinc2_10 30 15 53 51 53 Click here
17 steinc2_10 10 25 59 59 59 Click here
18 steinc2_10 30 25 53 51 53 Click here
19 steinc2_100 10 5 328 328 328 Click here
20 steinc2_100 30 5 328 328 328 Click here
21 steinc2_100 10 15 604 604 604 Click here
22 steinc2_100 30 15 546 533 546 Click here
23 steinc2_100 10 25 604 604 604 Click here
24 steinc2_100 30 25 546 533 546 Click here
25 steinc3_10 10 5 151 151 151 Click here
26 steinc3_10 30 5 95 95 95 Click here
27 steinc3_10 10 15 289 273 288 Click here
28 steinc3_10 30 15 129 129 129 Click here
29 steinc3_10 10 25 289 288 288 Click here
30 steinc3_10 30 25 129 129 129 Click here
31 steinc3_100 10 5 1519 1519 1519 Click here
32 steinc3_100 30 5 968 968 968 Click here
33 steinc3_100 10 15 2971 2970 2970 Click here
34 steinc3_100 30 15 1343 1238 1343 Click here
35 steinc3_100 10 25 2979 2936 2969 Click here
36 steinc3_100 30 25 1343 1296 1296 Click here
37 steinc4_10 10 5 115 115 115 Click here
38 steinc4_10 30 5 84 84 84 Click here
39 steinc4_10 10 15 336 333 335 Click here
40 steinc4_10 30 15 134 134 134 Click here
41 steinc4_10 10 25 341 325 335 Click here
42 steinc4_10 30 25 136 134 136 Click here
43 steinc4_100 10 5 1148 1148 1148 Click here
44 steinc4_100 30 5 854 854 854 Click here
45 steinc4_100 10 15 3458 3390 3456 Click here
46 steinc4_100 30 15 1380 1376 1376 Click here
47 steinc4_100 10 25 3504 3420 3432 Click here
48 steinc4_100 30 25 1396 1336 1396 Click here
49 steinc5_10 10 5 258 258 258 Click here
50 steinc5_10 30 5 154 154 154 Click here
51 steinc5_10 10 15 494 467 478 Click here
52 steinc5_10 30 15 182 181 182 Click here
53 steinc5_10 10 25 495 482 482 Click here
54 steinc5_10 30 25 183 178 181 Click here
55 steinc5_100 10 5 2600 2600 2600 Click here
56 steinc5_100 30 5 1584 1584 1584 Click here
57 steinc5_100 10 15 5032 4814 4834 Click here
58 steinc5_100 30 15 1857 1830 1837 Click here
59 steinc5_100 10 25 5044 4808 4875 Click here
60 steinc5_100 30 25 1860 1845 1845 Click here

 

Table 2. Results obtained by BLS (Single-BLS and Multiple-BLS, respectively) in the above paper, corresponding to the second group of 72 instances,including 56 most challenging ones with unknown optimal results. 

No. Graph b h Best Known Single-BLS Multiple-BLS Results(AllC2)
1 steinc8_10 20 5 229 228 228 Click here
2 steinc8_10 50 5 116 113 116 Click here
3 steinc8_10 20 15 319 316 326 Click here
4 steinc8_10 50 15 166 164 167 Click here
5 steinc8_10 20 25 319 319 328 Click here
6 steinc8_10 50 25 166 164 171 Click here
7 steinc8_100 20 5 2368 2327 2341 Click here
8 steinc8_100 50 5 1220 1170 1201 Click here
9 steinc8_100 20 15 3306 3255 3378 Click here
10 steinc8_100 50 15 1705 1721 1763 Click here
11 steinc8_100 20 25 3340 3297 3392 Click here
12 steinc8_100 50 25 1755 1620 1780 Click here
13 steinc9_10 20 5 283 280 284 Click here
14 steinc9_10 50 5 146 144 147 Click here
15 steinc9_10 20 15 354 365 376 Click here
16 steinc9_10 50 15 172 176 181 Click here
17 steinc9_10 20 25 353 375 379 Click here
18 steinc9_10 50 25 172 181 183 Click here
19 steinc9_100 20 5 2954 2891 2921 Click here
20 steinc9_100 50 5 1533 1536 1536 Click here
21 steinc9_100 20 15 3642 3744 3904 Click here
22 steinc9_100 50 15 1742 1852 1883 Click here
23 steinc9_100 20 25 3673 3907 3926 Click here
24 steinc9_100 50 25 1753 1882 1892 Click here
25 steinc10_10 20 5 372 365 385 Click here
26 steinc10_10 50 5 175 184 184 Click here
27 steinc10_10 20 15 509 535 545 Click here
28 steinc10_10 50 15 226 242 245 Click here
29 steinc10_10 20 25 513 533 547 Click here
30 steinc10_10 50 25 229 247 254 Click here
31 steinc10_100 20 5 3863 3896 4027 Click here
32 steinc10_100 50 5 1858 1918 1937 Click here
33 steinc10_100 20 15 5253 5491 5687 Click here
34 steinc10_100 50 15 2415 2555 2555 Click here
35 steinc10_100 20 25 5331 5542 5642 Click here
36 steinc10_100 50 25 2472 2510 2511 Click here
37 steinc13_10 20 5 439 439 439 Click here
38 steinc13_10 100 5 246 240 248 Click here
39 steinc13_10 20 15 439 439 439 Click here
40 steinc13_10 100 15 303 296 308 Click here
41 steinc13_10 20 25 439 439 439 Click here
42 steinc13_10 100 25 302 300 307 Click here
43 steinc13_100 20 5 4463 4463 4463 Click here
44 steinc13_100 100 5 2544 2558 2558 Click here
45 steinc13_100 20 15 4463 4463 4463 Click here
46 steinc13_100 100 15 3111 3220 3236 Click here
47 steinc13_100 20 25 4463 4463 4463 Click here
48 steinc13_100 100 25 3136 3092 3248 Click here
49 steinc14_10 20 5 648 648 648 Click here
50 steinc14_10 100 5 344 366 367 Click here
51 steinc14_10 20 15 648 648 648 Click here
52 steinc14_10 100 15 377 396 399 Click here
53 steinc14_10 20 25 648 648 648 Click here
54 steinc14_10 100 25 377 394 397 Click here
55 steinc14_100 20 5 6566 6566 6566 Click here
56 steinc14_100 100 5 3503 3333 3824 Click here
57 steinc14_100 20 15 6566 6566 6566 Click here
58 steinc14_100 100 15 3929 4048 4122 Click here
59 steinc14_100 20 25 6566 6566 6566 Click here
60 steinc14_100 100 25 3897 4120 4120 Click here
61 steinc15_10 20 5 1211 1206 1213 Click here
62 steinc15_10 100 5 435 414 451 Click here
63 steinc15_10 20 15 1248 1248 1248 Click here
64 steinc15_10 100 15 515 545 548 Click here
65 steinc15_10 20 25 1248 1248 1248 Click here
66 steinc15_10 100 25 520 539 546 Click here
67 steinc15_100 20 5 12306 12121 12213 Click here
68 steinc15_100 100 5 4379 4378 4378 Click here
69 steinc15_100 20 15 12533 12533 12533 Click here
70 steinc15_100 100 15 5355 5642 5770 Click here
71 steinc15_100 20 25 12533 12533 12533 Click here
72 steinc15_100 100 25 5393 5663 5703 Click here

 

Table 3. Results obtained by BLS (Single-BLS and Multiple-BLS, respectively) in the above paper, corresponding to the third group of 108 instances,all with collected revenues already reaching the upper bound. 

No. Graph b h UB Single-BLS Multiple-BLS Results(AllC3)
1 steinc6_10 20 5 27 27 27 Click here
2 steinc6_10 50 5 27 27 27 Click here
3 steinc6_10 20 15 27 27 27 Click here
4 steinc6_10 50 15 27 27 27 Click here
5 steinc6_10 20 25 27 27 27 Click here
6 steinc6_10 50 25 27 27 27 Click here
7 steinc6_100 20 5 274 274 274 Click here
8 steinc6_100 50 5 274 274 274 Click here
9 steinc6_100 20 15 274 274 274 Click here
10 steinc6_100 50 15 274 274 274 Click here
11 steinc6_100 20 25 274 274 274 Click here
12 steinc6_100 50 25 274 274 274 Click here
13 steinc7_10 20 5 49 49 49 Click here
14 steinc7_10 50 5 49 49 49 Click here
15 steinc7_10 20 15 59 59 59 Click here
16 steinc7_10 50 15 59 59 59 Click here
17 steinc7_10 20 25 59 59 59 Click here
18 steinc7_10 50 25 59 59 59 Click here
19 steinc7_100 20 5 503 503 503 Click here
20 steinc7_100 50 5 503 503 503 Click here
21 steinc7_100 20 15 604 604 604 Click here
22 steinc7_100 50 15 604 604 604 Click here
23 steinc7_100 20 25 604 604 604 Click here
24 steinc7_100 50 25 604 604 604 Click here
25 steinc11_10 20 5 27 27 27 Click here
26 steinc11_10 100 5 27 27 27 Click here
27 steinc11_10 20 15 27 27 27 Click here
28 steinc11_10 100 15 27 27 27 Click here
29 steinc11_10 20 25 27 27 27 Click here
30 steinc11_10 100 25 27 27 27 Click here
31 steinc11_100 20 5 274 274 274 Click here
32 steinc11_100 100 5 274 274 274 Click here
33 steinc11_100 20 15 274 274 274 Click here
34 steinc11_100 100 15 274 274 274 Click here
35 steinc11_100 20 25 274 274 274 Click here
36 steinc11_100 100 25 274 274 274 Click here
37 steinc12_10 20 5 59 59 59 Click here
38 steinc12_10 100 5 59 59 59 Click here
39 steinc12_10 20 15 59 59 59 Click here
40 steinc12_10 100 15 59 59 59 Click here
41 steinc12_10 20 25 59 59 59 Click here
42 steinc12_10 100 25 59 59 59 Click here
43 steinc12_100 20 5 604 604 604 Click here
44 steinc12_100 100 5 604 604 604 Click here
45 steinc12_100 20 15 604 604 604 Click here
46 steinc12_100 100 15 604 604 604 Click here
47 steinc12_100 20 25 604 604 604 Click here
48 steinc12_100 100 25 604 604 604 Click here
49 steinc16_10 100 5 27 27 27 Click here
50 steinc16_10 200 5 27 27 27 Click here
51 steinc16_10 100 15 27 27 27 Click here
52 steinc16_10 200 15 27 27 27 Click here
53 steinc16_10 100 25 27 27 27 Click here
54 steinc16_10 200 25 27 27 27 Click here
55 steinc16_100 100 5 274 274 274 Click here
56 steinc16_100 200 5 274 274 274 Click here
57 steinc16_100 100 15 274 274 274 Click here
58 steinc16_100 200 15 274 274 274 Click here
59 steinc16_100 100 25 274 274 274 Click here
60 steinc16_100 200 25 274 274 274 Click here
61 steinc17_10 100 5 59 59 59 Click here
62 steinc17_10 200 5 59 59 59 Click here
63 steinc17_10 100 15 59 59 59 Click here
64 steinc17_10 200 15 59 59 59 Click here
65 steinc17_10 100 25 59 59 59 Click here
66 steinc17_10 200 25 59 59 59 Click here
67 steinc17_100 100 5 604 604 604 Click here
68 steinc17_100 200 5 604 604 604 Click here
69 steinc17_100 100 15 604 604 604 Click here
70 steinc17_100 200 15 604 604 604 Click here
71 steinc17_100 100 25 604 604 604 Click here
72 steinc17_100 200 25 604 604 604 Click here
73 steinc18_10 100 5 439 439 439 Click here
74 steinc18_10 200 5 439 439 439 Click here
75 steinc18_10 100 15 439 439 439 Click here
76 steinc18_10 200 15 439 439 439 Click here
77 steinc18_10 100 25 439 439 439 Click here
78 steinc18_10 200 25 439 439 439 Click here
79 steinc18_100 100 5 4463 4463 4463 Click here
80 steinc18_100 200 5 4463 4463 4463 Click here
81 steinc18_100 100 15 4463 4463 4463 Click here
82 steinc18_100 200 15 4463 4463 4463 Click here
83 steinc18_100 100 25 4463 4463 4463 Click here
84 steinc18_100 200 25 4463 4463 4463 Click here
85 steinc19_10 100 5 648 648 648 Click here
86 steinc19_10 200 5 648 648 648 Click here
87 steinc19_10 100 15 648 648 648 Click here
88 steinc19_10 200 15 648 648 648 Click here
89 steinc19_10 100 25 648 648 648 Click here
90 steinc19_10 200 25 648 648 648 Click here
91 steinc19_100 100 5 6566 6566 6566 Click here
92 steinc19_100 200 5 6566 6566 6566 Click here
93 steinc19_100 100 15 6566 6566 6566 Click here
94 steinc19_100 200 15 6566 6566 6566 Click here
95 steinc19_100 100 25 6566 6566 6566 Click here
96 steinc19_100 200 25 6566 6566 6566 Click here
97 steinc20_10 100 5 1248 1248 1248 Click here
98 steinc20_10 200 5 1248 1248 1248 Click here
99 steinc20_10 100 15 1248 1248 1248 Click here
100 steinc20_10 200 15 1248 1248 1248 Click here
101 steinc20_10 100 25 1248 1248 1248 Click here
102 steinc20_10 200 25 1248 1248 1248 Click here
103 steinc20_100 100 5 12533 12533 12533 Click here
104 steinc20_100 200 5 12533 12532 12533 Click here
105 steinc20_100 100 15 12533 12533 12533 Click here
106 steinc20_100 200 15 12533 12533 12533 Click here
107 steinc20_100 100 25 12533 12533 12533 Click here
108 steinc20_100 200 25 12533 12533 12533 Click here

 

Notes:

1. All the STPRBH graphs 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 BLS 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 BLS 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 BLS algorithm

Consumed budget