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 条

[11]

JOHNSON DS, 2000, P 11 ACM SIAM S DISC

[12]

Klau GW, 2004, LECT NOTES COMPUT SC, V3102, P1304

[13]

Ljubic I., 2006, MATH PROGAMMING

[14]

Ljubic I., 2004, THESIS

[15]

Ljubic I., 2005, P ALENEX 7 WORKSH AL

[16] A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks [J].

Montemanni, R. ;

Leggieri, V. .

MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2011, 74 (03) :327-342

[17]

Montemanni R., 2010, ELECT NOTES DISCRETE, V36, P215

[18] Mixed integer formulations for the probabilistic minimum energy broadcast problem in wireless networks [J].

Montemanni, Roberto ;

Leggieri, Valeria ;

Triki, Chefi .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 190 (02) :578-585

[19] THE NODE-WEIGHTED STEINER TREE PROBLEM [J].

SEGEV, A .

NETWORKS, 1987, 17 (01) :1-17

[20]

Tuncbag N., 2012, NUCL ACIDS RES, V15

← 1 2 →