Premium
Models and heuristics for the k ‐degree constrained minimum spanning tree problem with node‐degree costs
Author(s) -
Duhamel Christophe,
Gouveia Luís,
Moura Pedro,
de Souza Maurício
Publication year - 2012
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.20445
Subject(s) - grasp , degree (music) , mathematical optimization , linear programming , integer programming , heuristics , minimum spanning tree , node (physics) , spanning tree , mathematics , heuristic , linear programming relaxation , path (computing) , tree (set theory) , computer science , algorithm , discrete mathematics , combinatorics , physics , acoustics , engineering , programming language , structural engineering
The k ‐Degree constrained Minimum Spanning Tree Problem ( k ‐DMSTP) consists in finding a minimal cost spanning tree satisfying the condition that every node has a degree no greater than a fixed value k . Here we consider an extension where besides the edge costs, a concave cost function is associated to the degree of each node. Several integer linear programming formulations based on reformulation techniques are presented and their linear programming relaxations are compared. A GRASP heuristic to obtain feasible solutions for the problem together with a Path Relinking strategy is also described. We include computational results using instances with up to 200 nodes that give an empirical assessment of the linear programming bounds of the different models as well as the ability of using these models to solve the problems by using an Integer Linear Programming package. The results also show that the proposed GRASP heuristic appears to perform rather well for this type of problems. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012