Lower bounds for the Quadratic Minimum Spanning Tree Problem based on reduced cost computation

• Review and analyzing different lower bounding strategies for the QMSTP.
• Using the meaning of reduced costs to develop new bounds.
• Developing two new bounds based on a reformulation scheme.
• Developing a new bound based on a second level of the RLT.
• Devising some efficient dual-ascent algorithms to solve the proposed models.

The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MSTP whose cost considers also the interaction between every pair of edges of the tree. In this paper we review different strategies found in the literature to compute a lower bound for the QMSTP and develop new bounds based on a reformulation scheme and some new mixed 0–1 linear formulations that result from a reformulation–linearization technique (RLT). The new bounds take advantage of an efficient way to retrieve dual information from the MSTP reduced cost computation. We compare the new bounds with the other bounding procedures in terms of both overall strength and computational effort. Computational experiments indicate that the dual-ascent procedure applied to the new RLT formulation provides the best bounds at the price of increased computational effort, while the bound obtained using the reformulation scheme seems to reasonably tradeoff between the bound tightness and computational effort.