QMSTools

QMSTools is an open-source software package focused on the Quadratic Minimum Spanning Tree (QMST) problem and related variants. The QMST problem generalizes the classical minimum spanning tree by incorporating a quadratic cost term that captures interactions between pairs of edges, providing a richer model for network design and infrastructure planning.

The toolbox assembles essential components for QMST research and application. It includes data structures for representing undirected graphs, supports definition of linear and quadratic costs, and offers utilities to generate or load benchmark instances. QMSTools provides a range of solvers, from exact methods that leverage problem structure and MILP formulations to heuristic and metaheuristic approaches designed for larger instances. Typical algorithms encompass exact search techniques and local-search families such as tabu search and simulated annealing, along with other practical heuristics.

Designed with reproducibility in mind, QMSTools emphasizes standardized input and output formats, enabling researchers to reproduce experiments and compare performance across methods. Outputs commonly tracked include the best-found objective value, the corresponding edge set, and runtime, with options for additional diagnostic information.

The project is commonly used in academia and advanced network optimization practice. It serves as a platform for experimentation, benchmarking, and method development in QMST research, as well as an educational resource for students studying combinatorial optimization and related topics.

Availability and community: QMSTools is hosted in an open-source repository that provides documentation, example datasets, and usage guidelines. It is intended to be extensible, allowing users to implement new solvers or plug in custom instance generators, contributing to ongoing development and methodological comparisons in QMST research.