This page collects benchmark instances and best known results.
An undirected graph G = (V,E) is given, with a linear cost function c on the edges and a quadratic cost function q on the pairs of edges.
Find a spanning tree of minimum total cost.
Test set employed in R. Cordone and G. Passeri, Solving the Quadratic Minimum Spanning Tree Problem, Applied Mathematics and Computation 218 (23), Pages 11597-11612, August 2012.
All instances are in MathProg (i.e. AMPL) format. Their names follow a self-evident convention:
For example: n010d033C010c001Q010q001s-3i1.txt stands for 10 vertices, 33% (10-1)10/2 = 15 edges, linear anche quadratic costs in [1;100]; random seed -3; first instance
The upper bounds have been obtained by Tabu Search QMST-TS on the following benchmarks:
The lower bounds have been obtained by branch-and-bound QMST-BB on the following benchmarks:
The computational times refer to a 2.6 GHz Intel Pentium Core 2 Duo E6700 with 2 GB of RAM.