METAHEURISTIC APPROACHES FOR THE QUADRATIC MINIMUM SPANNING TREE PROBLEM

Authors

  • Gintaras Palubeckis Kaunas University of Technology
  • Dalius Rubliauskas Kaunas University of Technology
  • Aleksandras Targamadz˙ Kaunas University of Technology

Keywords:

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

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.

Downloads

Published

2010-12-28

Issue

Section

Articles