A divide and conquer matheuristic algorithm for the Prize-collecting Steiner Tree Problem
A divide and conquer matheuristic algorithm for the Prize-collecting Steiner Tree Problem
复制标题
DOI：
10.1016/j.cor.2015.12.015
复制
发表时间：
2016-06-01
影响因子：
4.6
通讯作者：
Montemanni, Roberto
中科院分区：
文献类型：
--
作者：
Akhmedov, Murodzhon;Kwee, Ivo;Montemanni, Roberto
获奖斯坦纳树问题(PCSTP)是图论和组合优化中的一个著名问题。它已成功地应用于解决光纤、燃气管网设计等实际问题。在这项工作中，我们专注于它在生物学中的应用，以完成对基因的功能分析。在基因组学中，分析大型网络来推断隐藏的知识是很常见的。由于PCSTP的NP-Hard特性，如果可能的话，对于如此庞大的情况，获得精确解的计算代价很高。因此，需要快速高效的数学算法来挖掘和理解巨型生物图中隐藏的信息。在本研究中，我们提出了一种基于聚类算法的数学方法。该方法的主要目标是在不损失太多解质量的情况下，将当前可用的精确方法扩大到大型图实例的适用性。提出的数学方法由预处理程序、启发式聚类算法和PCSTP的精确求解器组成，适用于子图。我们在真实的生物学基准实例上测试了该方法的性能，并将其结果与没有启发式聚类的精确求解器的结果进行了比较。我们在较短的执行时间内得到解，且最优性差距可以忽略不计。这使得用目前可用的精确解算器分析非常大的生物网络成为可能。(C)2015爱思唯尔有限公司。保留所有权利。
The Prize-collecting Steiner Tree Problem (PCSTP) is a well-known problem in graph theory and combinatorial optimization. It has been successfully applied to solve real problems such as fiber-optic and gas distribution networks design. In this work, we concentrate on its application in biology to perform a functional analysis of genes. It is common to analyze large networks in genomics to infer a hidden knowledge. Due to the NP-hard characteristics of the PCSTP, it is computationally costly, if possible, to achieve exact solutions for such huge instances. Therefore, there is a need for fast and efficient matheuristic algorithms to explore and understand the concealed information in huge biological graphs. In this study, we propose a matheuristic method based on clustering algorithm. The main target of the method is to scale up the applicability of the currently available exact methods to large graph instances, without loosing too much on solution quality. The proposed matheuristic method is composed of a preprocessing procedures, a heuristic clustering algorithm and an exact solver for the PCSTP, applied on sub-graphs. We examine the performance of the proposed method on real-world benchmark instances from biology, and compare its results with those of the exact solver alone, without the heuristic clustering. We obtain solutions in shorter execution time and with negligible optimality gaps. This enables analyzing very large biological networks with the currently available exact solvers. (C) 2015 Elsevier Ltd. All rights reserved.