Name
Abstract | ||
|---|---|---|
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 |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1002/net.v50:1 | Networks |
Keywords | Field | DocType |
lagrangian lower bound,relax-and-cut lower bound,lagrangian non-delayed relax-and-cut algorithm,tree problem,random cost dcmstp instance,kruskal style algorithm,lagrangian relaxation,valid dcmstp upper bound,lower bound,plane algorithm,degree-constrained minimum,lagrangian information,minimum spanning tree | Mathematical optimization,Combinatorics,Search algorithm,Upper and lower bounds,Polytope,Linear programming,Spanning tree,Lagrangian relaxation,Kruskal's algorithm,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
50 | 1 | 0028-3045 |
Citations | PageRank | References |
13 | 0.86 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandre Salles da Cunha | 1 | 242 | 22.32 |
| Abilio Lucena | 2 | 362 | 34.05 |