MODELS AND ALGORITHMS FOR THE DIAMETER CONSTRAINED MINIMUM SPANNING TREE PROBLEM / MODELOS E ALGORITMOS PARA O PROBLEMA DA ÁRVORE GERADORA DE CUSTO MÍNIMO COM RESTRIÇÃO DE DIÂMETRO

AUTOR(ES)
DATA DE PUBLICAÇÃO

2006

RESUMO

In this work, models and approximation algorithms to solve the Diameter Constrained Minimum Spanning Tree Problem (AGMD) are proposed. This problem typically models network design applications where all vertices must communicate with each other at a minimum cost, while meeting a given quality requirement. The formulations proposed by Achuthan and Caccetta are strengthened with valid inequalities. A lagrangean relaxation is proposed for the multicommodity flow model developed by Gouveia and Magnanti. Adaptations are made in the constructive heuristics proposed by Deo and Abdalla and by Raidl and Julstrom. Four local search procedures, a GRASP algorithm and a hybrid heuristic are proposed. Upper bounds within 2% of the optimal solution values are obtained for the two classes of instances used by Gouveia and Magnanti and by Santos, Lucena and Ribeiro. Moreover, stronger upper bounds are reported for 11 instances in complete graphs used by Raidl, Julstrom and Gruber

ASSUNTO(S)

hybrid heuristics lagrangean relaxation relaxacao lagrangeana minimum spanning tree arvore geradora de custo minimo heuristicas hibridas meta-heuristicas projeto redes meta-heuristics network design

Documentos Relacionados