Premium
Lower and upper bounds for the degree‐constrained minimum spanning tree problem
Author(s) -
da Cunha Alexandre Salles,
Lucena Abilio
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20166
Subject(s) - polytope , combinatorics , mathematics , minimum spanning tree , spanning tree , degree (music) , upper and lower bounds , linear programming relaxation , cutting plane method , tree (set theory) , matching (statistics) , lagrangian relaxation , relaxation (psychology) , euclidean geometry , linear programming , mathematical optimization , integer programming , psychology , mathematical analysis , social psychology , statistics , physics , geometry , acoustics
In this paper, we propose a Lagrangian Non‐Delayed Relax‐and‐Cut algorithm for the Degree‐Constrained Minimum Spanning Tree Problem (DCMSTP). Since degree‐constrained trees are the common vertices of the Spanning Tree and the b‐Matching polytopes, strengthened DCMSTP lower bounds are generated through the use of Blossom Inequalities (BIs). BIs are facet defining for the b‐Matching Polytope and, to the best of our knowledge, have never been used before for DCMSTP. Lagrangian information is also used here, in a Kruskal style algorithm (followed by local search) to obtain valid DCMSTP upper bounds. Whenever optimality could not be proven by Relax‐and‐Cut alone, Lagrangian lower bounds are carried over to a cutting plane algorithm, without the need for solving any separation problem. This is accomplished after identifying, at Relax‐and‐Cut, a small set of attractive Subtour Elimination Constraints and BIs. Computational results, on Euclidean and on random cost DCMSTP instances, indicate that our Relax‐and‐Cut lower bounds either dominate or else are competitive with linear programming and Lagrangian relaxation lower bounds found in the literature. Furthermore, our upper bounds appear competitive with the best in the literature. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 55–66 2007