Efficient lower and upper bounds for the weight-constrained minimum spanning tree problem using simple Lagrangian based
- PDF / 3,232,346 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 173 Views
Efficient lower and upper bounds for the weight‑constrained minimum spanning tree problem using simple Lagrangian based algorithms Cristina Requejo1 · Eulália Santos2 Received: 28 November 2016 / Revised: 3 January 2018 / Accepted: 10 September 2018 © Springer-Verlag GmbH Germany, part of Springer Nature 2018
Abstract The weight-constrained minimum spanning tree problem (WMST) is a combinatorial optimization problem for which simple but effective Lagrangian based algorithms have been used to compute lower and upper bounds. In this work we present several Lagrangian based algorithms for the WMST and propose two new algorithms, one incorporates cover inequalities. A uniform framework for deriving approximate solutions to the WMST is presented. We undertake an extensive computational experience comparing these Lagrangian based algorithms and show that these algorithms are fast and present small integrality gap values. The two proposed algorithms obtain good upper bounds and one of the proposed algorithms obtains the best lower bounds to the WMST. Keywords Weighted minimum spanning tree · Minimum spanning tree · Lagrangian based algorithms
1 Introduction Consider an undirected complete graph G = (V, E) , with node set V = {0, 1, … , n − 1} and edge set E = {{i, j}, i, j ∈ V, i ≠ j} . Associated with each edge e = {i, j} ∈ E consider positive integer costs ce and weights we . The Weightconstrained Minimum Spanning Tree problem (WMST) is to find a spanning tree ∑ T = (V, ET ) in G, ET ⊂ E , of minimum cost C(T) = e∈ET ce and with total weight ∑ W(T) = e∈ET we not exceeding a given limit W. An additional constraint to the * Cristina Requejo [email protected] Eulália Santos [email protected] 1
Department of Mathematics and CIDMA, University of Aveiro, 3810‑193 Aveiro, Portugal
2
ISLA-Higher Institute of Leiria and Santarém, 2414‑017 Leiria, Portugal
13
Vol.:(0123456789)
C. Requejo, E. Santos
Minimum Spanning Tree problem (MST) such as the weight constraint (the total tree weight W(T) can not exceed a given limit W) turns this constrained MST into a NP-hard problem. The WMST is a NP-hard combinatorial optimization problem (Aggarwal et al. 1982; Yamada et al. 2005). The WMST appears in several real applications where the weight restrictions are mainly concerned with a limited budget on installation/upgrading costs. In this case, weights we represent the installation/upgrading cost of the link e = {i, j} ∈ E and ce represent the link nominal cost/length. A classical application arises in the areas of communication networks and network design, in which information is broadcasted over a minimum spanning tree, and is related with the upgrade and/or design of the physical systems when there is a pre-specified budget restriction (Henn 2007). The WMST has received several different designations. It was first mentioned in Aggarwal et al. (1982) as the MST problem subject to a side constraint, where MST stands for Minimal Spanning Tree. Besides the common designation as a WMST, the most common designation is as
Data Loading...
