An Evolutionary Algorithm Based on CMSA for Rooted Max Tree Coverage
针对有根最大树覆盖问题，首次提出多项式规模混合整数线性规划，并基于CMSA元启发式开发简单进化算法，实验表明该算法在小规模实例中几乎总能找到最优解，大规模实例中优于CPLEX和贪心算法。
The rooted max tree coverage (MTC) problem has wide applications in areas, such as network design and vehicle routing. Given a graph with non-negative costs defined on edges, a vertex used as the root, and a budget, the rooted MTC problem asks to find a tree containing the root and having total cost at most the budget, so that the number of vertices spanned by the tree is maximized. Rooted MTC is NP-hard and has constant factor approximation algorithms. However, the existing approximation algorithms for rooted MTC are very complicated and hard to be implemented practically. In this article, we formulate a polynomial size mixed integer linear program (MILP) for rooted MTC for the first time. Based on this, we develop a simple evolutionary algorithm for rooted MTC (called CMSA-MTC) using the CMSA meta-heuristic, where construct, merge, solve, and adapt (CMSA) is a meta-heuristic proposed recently. Experimental results show that CMSA-MTC has very good practical performance. For the small size instances of the problem, CMSA-MTC almost always finds the optimal solutions. For the large size instances, CMSA-MTC finds solutions better than that of CPLEX within the same running time and two additional greedy algorithms.