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.

Z. Naji-Azimi, M. Salari, B. Golden, S. Raghavan, P.Toth (2010). Variable Neighborhood Search for the Cost Constrained Minimum Label Spanning Tree and Label Constrained Minimum Spanning Tree Problems. COMPUTERS & OPERATIONS RESEARCH, 37, 1952-1964 [10.1016/j.cor.2009.12.013].

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

TOTH, PAOLO
2010

Abstract

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.
2010
Z. Naji-Azimi, M. Salari, B. Golden, S. Raghavan, P.Toth (2010). Variable Neighborhood Search for the Cost Constrained Minimum Label Spanning Tree and Label Constrained Minimum Spanning Tree Problems. COMPUTERS & OPERATIONS RESEARCH, 37, 1952-1964 [10.1016/j.cor.2009.12.013].
Z. Naji-Azimi; M. Salari; B. Golden; S. Raghavan; P.Toth
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/87197
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 9
social impact