A Comparison of Heuristic Methods for the Prize-Collecting Steiner Tree Problem and Their Application in Genomics

Murodzhon Akhmedov (), Ivo Kwee () and Roberto Montemanni ()
Additional contact information
Murodzhon Akhmedov: Dalle Molle Institute for Artificial Intelligence (IDSIA-USI/SUPSI)
Ivo Kwee: Dalle Molle Institute for Artificial Intelligence (IDSIA-USI/SUPSI)
Roberto Montemanni: Dalle Molle Institute for Artificial Intelligence (IDSIA-USI/SUPSI)

A chapter in Operations Research Proceedings 2015, 2017, pp 101-108 from Springer

Abstract: 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.

Keywords: Minimum Span Tree; Mixed Integer Linear Programming; Minimum Span Tree Problem; Short Path Distance; Gene Interaction Network (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-42902-1_14

Ordering information: This item can be ordered from
http://www.springer.com/9783319429021

DOI: 10.1007/978-3-319-42902-1_14

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().