Tabu search with strategic oscillation for the quadratic minimum spanning tree

Abstract

The quadratic minimum spanning tree problem consists of determining a spanning tree that minimizes the sum of costs of the edges and pairs of edges in the tree. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated metaheuristics. This article presents a simple Tabu Search (TS) for this problem that incorporates Strategic Oscillation (SO) by alternating between constructive and destructive phases. The commonalties shared by this strategy and the more recently introduced methodology called iterated greedy search are shown and implications of their differences regarding the use of memory structures are identified. Extensive computational experiments reveal that the proposed SO algorithm with embedded TS is highly effective for solving complex instances of the problem as compared with the best metaheuristics in the literature. A hybrid method that proves similarly effective for problem instances that are both simple and complex is introduced.

Keywords:

• Tabu search
• strategic oscillation
• adaptive memory programming
• quadratic minimum spanning tree
• iterated greedy