A Matheuristic Algorithm for the Prize-collecting Steiner Tree Problem

被引：0

作者：

Akhmedov, Murodzhon ^{[1
]}

Kwee, Ivo ^{[2
]}

Montemanni, Roberto ^{[1
]}

机构：

[1] USI SUPSI, Dalle Molle Inst Artificial Intelligence IDSIA, Galleria 2, CH-6928 Manno, Switzerland

[2] IOR, CH-6500 Bellinzona, Switzerland

来源：

2015 3rd International Conference on Information and Communication Technology (ICoICT) | 2015年

关键词：

Prize-collecting Steiner Tree Problem; Combinatorial Optimization; Matheuristics; NETWORKS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Prize-collecting Steiner Tree Problem (PCSTP) is a well studied problem in combinatorial optimization. It has a wide range of applications in the literature, for instance in fiber optics such as gas distribution and district heating. In this study, we focus on its application in functional analysis of genes on bio-genetic graphs. In bio-genetics its extremely possible to have a huge graphs to interpret. Since the PCSTP is NP-hard, it is time consuming to obtain solutions for large instances. Thus, there is a need for efficient and fast heuristic algorithms to discover the hidden knowledge behind the vast bio-genetic networks. We propose a matheuristic composed of heuristic clustering algorithm and existing mixed integer liner programming to solve PCSTP. We evaluated the performance of our matheuristic on available real-world benchmark instances from the biology and compared it with existing heuristic approach in the literature. With respect to heuristic results, we obtained solutions with similar or better objective function values. On the other hand the existing heuristic solved the benchmark instances with smaller running time compared to proposed matheuristic.

引用

页码：408 / 412

页数：5

共 20 条

[1]

Akhmedov M., 2014, LECT NOTES MANAGEMEN

[2]

[Anonymous], 2014, GUR OPT REF MAN

[3]

Barta J., 2010, ELECT NOTES DISCRETE, V36, P463

[4]

Beasley J. E., 1990, J OPERATIONAL RES SO

[5]

Becheta M. B., 2010, PNAS, V108

[6]

Bienstock D., 1993, MATH PROGAMMING, V59

[7] Local search with perturbations for the prize-collecting Steiner tree problem in graphs [J].

Canuto, SA ;

Resende, MGC ;

Ribeiro, CC .

NETWORKS, 2001, 38 (01) :50-58

[8]

Dijkstra E.W., 1959, NUMER MATH, V1, DOI DOI 10.1007/BF01386390

[9] Identifying functional modules in protein-protein interaction networks:: an integrated exact approach [J].

Dittrich, Marcus T. ;

Klau, Gunnar W. ;

Rosenwald, Andreas ;

Dandekar, Thomas ;

Mueller, Tobias .

BIOINFORMATICS, 2008, 24 (13) :I223-I231

[10]

Haouari M., 2010, ELECT NOTES DISCRETE, V36

← 1 2 →