Meta-heuristics for the Generator Tree Problem with Minimal Labeling and Budget Constraints

The Budgeted Minimum Labeling Spanning Tree Problem is a connectivity problem in edge-labeled graphs, aiming to find a spanning tree that minimizes the number of labels used, while respecting upper bounds on the number of edges allowed per label. To address this problem, two heuristic methods were proposed, based on the GRASP and BRKGA metaheuristics, along with a cut-based formulation and a branch-and-cut algorithm, used to validate the heuristic methods. Computational experiments showed that the GRASP-based method found the optimal solution in all instances where the formulation converged within the time limit. It also outperformed the BRKGA-based method in both solution quality and computational performance.