Dataset for Minimum Spanning Tree Problem with Conflict Constraints

This dataset provides all benchmark instances and source code used in the article “Minimum Spanning Tree Problem with Conflict Constraints (MSTC)”. It enables full reproducibility of the computational experiments reported in the paper and serves as a reference collection for future studies on MSTC and related combinatorial optimization problems. It contains the Restricted Test Set (RTS) of 48 small–medium instances, and the Extended Random Set (ERS) of 335 large-scale instances. The dataset also includes the source code of the instance generator for reproducibility of the MSTC instances, and the source code of the Stable Set Based Branch-and-bound Algorithm for the MSTC problem. Both source codes are written in C++ 17. These instances were generated to benchmark exact and heuristic algorithms for the MSTC problem. Researchers may reuse or extend the dataset to test new formulations, relaxations, or heuristics. STRONG and WEAK formulations are included to be used for benchmarking in both multi-thread and single-thread settings. They are solved with commercial solver Gurobi 10.0.3, which is called from a Python program. All data are provided in plain-text format for easy parsing. All experiments were executed on Windows 10 using Visual Studio 2022 (MSVC v17, C++17), as detailed in the article’s Online Supplement.