The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm


ÖNCAN T., Punnen A. P.

COMPUTERS & OPERATIONS RESEARCH, vol.37, no.10, pp.1762-1773, 2010 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 37 Issue: 10
  • Publication Date: 2010
  • Doi Number: 10.1016/j.cor.2010.01.004
  • Journal Name: COMPUTERS & OPERATIONS RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.1762-1773
  • Galatasaray University Affiliated: Yes

Abstract

In this paper we consider the quadratic minimum spanning tree problem (QMSTP) which is known to be NP-hard. Given a complete graph, the QMSTP consists of finding a minimum spanning tree (MST) where interaction costs between pairs of edges are prescribed. A Lagrangian relaxation procedure is devised and an efficient local search algorithm with tabu thresholding is developed. Computational experiments are reported on standard test instances, randomly generated test instances and quadratic assignment problem (QAP) instances from the QAPLIB by using a transformation scheme. The local search heuristic yields very good performance and the Lagrangian relaxation procedure gives the tightest lower bounds for all instances when compared to previous lower bounding approaches. (C) 2010 Elsevier Ltd. All rights reserved.