交大主頁 | OA系統 | 信息門戶 | 教師主頁 | 思源信箱 | 資料下載
當前位置: 學院首頁>>新聞資訊>>通知公告>>正文

巴西科学院院士Celso Ribeiro教授学术报告通知

2019年07月11日 16:35  點擊:[]


報告題目: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日

上一條:周曉舟副教授講座 下一條:西安交通大學經濟與金融學院2019年夏令營活動安排

關閉

您是本站第
04519677
位訪問者,當前 人在線
版權所有:西安交通大學經濟與金融學院
地址:陕西省西安市雁塔西路74号 电话:029-82656840 邮编:710061