Tabu Search with Ejection Chain for the Biobjective Adjacent-only Quadratic Spanning Tree

Abstract

Given an edge-weighted simple graph G, the minimum quadratic spanning tree problem consists in finding a spanning tree of G such that the sum of the weights of its edges plus the sum of the product of the weights of pairs of edges is minimum over all spanning trees of G. When the product of the weights of pairs of edges is calculated only for adjacent edges, the problem is called adjacent-only minimum quadratic spanning tree. This problem belongs to NP-hard. In this study we investigate the performance of a tabu search algorithm with ejection chain for the bi-objective version of this problem. An experiment with 168 instances is reported.