Variable Neighborhood Search for the Cost Constrained Minimum Label Spanning Tree and Label Constrained Minimum Spanning Tree Problems

Given an undirected graph whose edges are labeled or colored, edge weights indicating the cost of an edge, and a positive budget B, the goal of the Cost Constrained Minimum Label Spanning Tree (CCMLST) Problem is to find a spanning tree that uses the minimum number of labels while ensuring its cost does not exceed B. The Label Constrained Minimum Spanning Tree (LCMST) Problem is closely related to the CCMLST problem. Here, we are given a threshold K on the number of labels. The goal is to find a minimum weight spanning tree that uses at most K distinct labels. Both of these problems are motivated from the design of telecommunication networks and are known to be NP-complete. In this paper, we present a Variable Neighborhood Search (VNS) algorithm for the CCMLST problem. The VNS algorithm uses neighborhoods defined on the labels. We also adapt the VNS algorithm to the LCMST problem. We then test the VNS algorithm on existing data sets as well as a large-scale dataset based on TSPLIB instances ranging in size from 500 to 1000 nodes. The computational results show the effectiveness of the proposed algorithms.