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 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).

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).

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