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