A two-level solution approach for solving the generalized minimum spanning tree problem

Petrică C. Pop, Oliviu Matei, Cosmin Sabo and Adrian Petrovan

European Journal of Operational Research, 2018, vol. 265, issue 2, 478-487

Abstract: In this paper, we are addressing the generalized minimum spanning tree problem, denoted by GMSTP, which is a variant of the classical minimum spanning tree (MST) problem. The main characteristic of this problem is the fact that the vertices of the graph are partitioned into a given number of clusters and we are looking for a minimum-cost tree spanning a subset of vertices which includes exactly one vertex from each cluster. We describe a two-level solution approach for solving the GMSTP obtained by decomposing the problem into two logical and natural smaller subproblems: an upper-level (global) subproblem and a lower-level (local) subproblem and solving them separately. The goal of the first subproblem is to determine (global) trees spanning the clusters using a genetic algorithm with a diploid representation of the individuals, while the goal of the second subproblem is to determine the best tree (w.r.t. cost minimization), for the above mentioned global trees, spanning exactly one vertex from each cluster. The second subproblem is solved optimally using dynamic programming. Extensive computational results are reported and discussed for an often used set of benchmark instances. The obtained results show an improvement in the quality of the achieved solutions, and demonstrate the efficiency of our approach compared to the existing methods from the literature.

Keywords: Combinatorial optimization; Generalized minimum spanning tree problem; Genetic algorithms; Decomposition methods; Dynamic programming (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717307464
Full text for ScienceDirect subscribers only

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:eee:ejores:v:265:y:2018:i:2:p:478-487

DOI: 10.1016/j.ejor.2017.08.015

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().