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


ÖNCAN T. , Punnen A. P.

COMPUTERS & OPERATIONS RESEARCH, cilt.37, ss.1762-1773, 2010 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 37 Konu: 10
  • Basım Tarihi: 2010
  • Doi Numarası: 10.1016/j.cor.2010.01.004
  • Dergi Adı: COMPUTERS & OPERATIONS RESEARCH
  • Sayfa Sayıları: ss.1762-1773

Özet

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.