METAHEURISTIC APPROACHES FOR THE QUADRATIC MINIMUM SPANNING TREE PROBLEM

Gintaras Palubeckis, Dalius Rubliauskas, Aleksandras Targamadz˙

Abstract


Given an undirected graph with costs associated both with its edges and unordered pairs of edges, the quadratic minimum spanning tree problem asks to find a spanning tree that minimizes the sum of costs of all edges and pairs of edges in the tree. We present multistart simulated annealing, hybrid genetic and iterated tabu search algorithms for solving this problem. We report on computational experiments that compare these algorithms on random graphs of size up to 50 vertices. The results indicate that the iterated tabu search algorithm is superior to the other two approaches in terms of both solution quality and computation time.


Keywords


combinatorial optimization; quadratic minimum spanning tree; metaheuristics; simulated annealing; genetic algorithm; tabu search.

Full Text: PDF

Print ISSN: 1392-124X 
Online ISSN: 2335-884X