  Given an undirected graph with costs associated with each edge as well as
each pair of edges, the quadratic minimum spanning tree problem (QMSTP)
consists of determining a spanning tree of minimum total cost. This problem can
be used to model many real-life network design applications, in which both
routing and interference costs should be considered. For this problem, we
propose a three-phase search approach named TPS, which integrates 1) a
descent-based neighborhood search phase using two different move operators to
reach a local optimum from a given starting solution, 2) a local optima
exploring phase to discover nearby local optima within a given regional search
area, and 3) a perturbation-based diversification phase to jump out of the
current regional search area. Additionally, we introduce dedicated techniques
to reduce the neighborhood to explore and streamline the neighborhood
evaluations. Computational experiments based on hundreds of representative
benchmarks show that TPS produces highly competitive results with respect to
the best performing approaches in the literature by improving the best known
results for 31 instances and matching the best known results for the remaining
instances only except two cases. Critical elements of the proposed algorithms
are analyzed.
