报告题目：A GRASP with path-relinking heuristic for the prize collecting generalized minimum spanning tree

(带有路径重新链接启发式的GRASP方法在集奖广义最小生成树中的应用)

报告时间：2019年7月19日（星期五）上午9：30-11:00

报告地点：财经主楼八楼国际学术交流厅

报告摘要：

Given a graph with its vertex set partitioned into a set of groups, non-negative costs associated to its edges, and non-negative prizes associated to its vertices, the prize-collecting generalized minimum spanning tree problem consists in finding a subtree of this graph, spanning exactly one vertex of each group and minimizing the sum of the costs of the edges of the tree less the prizes of the selected vertices. It is a generalization of the NP-hard generalized minimum spanning tree optimization problem. We propose a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic for its approximate solution, incorporating path-relinking for search intensification and a restart strategy for search diversification. The hybridization of the GRASP with path-relinking and restarts heuristic with a data mining strategy that is applied along the GRASP iterations, after the elite set is modified and becomes stable, contributes to make the heuristic more robust. The computational experiments show that the heuristic developed in this work found very good solutions for test problems with up to 439 vertices. All input data for the test instances and detailed numerical results are made available from Mendeley Data.

给定一个图，它的顶点被划分为不同的组，赋予其每条边一个非负成本，每个顶点一个非负奖励，集奖广义最小生成树问题需要找到一个该图的子树，使其包含且仅包含每一组顶点中的一个点，同时最小化这个子树所有边的成本之和使其小于选定的一组顶点奖励之和。这个问题是对NP难问题广义最小生成树优化问题的一个推广。我们提出了一个启发式方法GRASP（Greedy Randomized Adaptive Search Procedure, 带自适应搜索步骤的随机贪婪方法）来求解得到它的近似解，这个方法包含路径重链接步骤以强化搜索以及一个重开始策略以分散化搜索。GRASP方法将路径重链接策略与重开始策略进行混合使得整个算法更加鲁棒，当备选集合修改后变得稳定时，GRASP方式基于数据挖掘策略沿着迭代步采用重开始策略。数值实验结果表明，我们提出的启发式方法针对一个拥有439个顶点的例子也可以找到非常好的解。所有测试例子的输入数据以及详细的数值结果可以在Mendeley Data上找到。

报告人简介：

Celso Ribeiro是Universidade Federal Fluminense (UFF)教授，巴西科学院院士，美国AT&T实验室中心的客座研究员，主要研究兴趣是离散优化、启发式方法、随机方法、并行计算、图与网络等，共出版专著六部，发表文章一百四十余篇，现任International Transactions in Operational Research (Wiley)杂志的主编，以及一些国际知名期刊的副主编。

经金学院

2019年7月11日