A Comparison of Heuristic Methods for the Prize-Collecting Steiner Tree Problem and Their Application in Genomics
The prize-collecting Steiner tree (PCST) problem is a broadly studied problem in combinatorial optimization. It has been used to model several real world problems related to utility networks. More recently, researchers have started using PCSTs to study bi
- PDF / 102,970 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 87 Downloads / 183 Views
Abstract The prize-collecting Steiner tree (PCST) problem is a broadly studied problem in combinatorial optimization. It has been used to model several real world problems related to utility networks. More recently, researchers have started using PCSTs to study biological networks. Biological networks are typically very large in size. This can create a considerable challenge for the available PCST solving methods. Taking this fact into account, we have developed methods for the PCST that efficiently scale up to large biological network instances. Namely, we have devised a heuristic method based on the Minimum Spanning Tree and a matheuristic method composed of a heuristic clustering phase and a solution phase. In this work, we provide a performance comparison for these methods by testing them on large gene interaction networks. Experimental results are reported for the methods, including running times and objective values of the solutions.
1 Introduction The prize-collecting Steiner tree is a well known problem in combinatorial optimization and graph theory. Within the concept of the PCST, given an undirected network G = (V , E), where nodes are associated with prizes pj ≥ 0 and arcs are associated with costs ce > 0, the goal is to construct a sub-graph G = (V , E ) that has a tree structure. The researchers have studied different variants of the PCST problem in the literature. One of the broadly studied variant is known as Goemans–Williamson M. Akhmedov (B) · I. Kwee · R. Montemanni Dalle Molle Institute for Artificial Intelligence (IDSIA-USI/SUPSI), Galleria 2, 6928 Manno, Switzerland e-mail: [email protected] I. Kwee e-mail: [email protected] R. Montemanni e-mail: [email protected] M. Akhmedov · I. Kwee Institute of Oncology Research (IOR), Via Vela 6, 6500 Bellinzona, Switzerland © Springer International Publishing Switzerland 2017 K.F. Dœrner et al. (eds.), Operations Research Proceedings 2015, Operations Research Proceedings, DOI 10.1007/978-3-319-42902-1_14
101
102
M. Akhmedov et al.
Minimization [1], where the objective is to identify a tree for a given graph by minimizing the total cost of arcs in a tree and minimizing the total prize of nodes excluded from the tree. This corresponds to the minimization of the following expression: GW (G ) =
e∈E
ce +
pv
(1)
v∈V /
The PCST has been successfully applied to model several real-world problems in utility networks. Recently, researchers have realized its application to biological networks for discovering the hidden knowledge [2]. Based on this idea, we have applied the PCST to gene interaction networks, where nodes correspond to genes and arcs represent the mutual information between genes. The PCST potentially captures the portion of graphs where genetic aberrations and mutations are highly present. Basically, biological interaction networks are large in size, and this can be remarkable challenge for existing PCST methods. By considering this fact in our previous studies, we have developed methods for the PCST that efficiently scale
Data Loading...
