Branch-and-cut and GRASP with hybrid local search for the multi-level capacitated minimum spanning tree problem.

Nenhuma Miniatura disponível
Data
2009
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
We propose efficient algorithms to compute tight lower bounds and high quality upper bounds for the Multi-Level Capacitated Minimum Spanning Tree problem. We first develop a branch-and-cut algorithm for the problem. This algorithm is able to solve instances of medium size and to provide tight lower bounds for larger ones. We then use the branch-and-cut within GRASP to evaluate subproblems during the search. The computational experiments conducted have improved best known lower and upper bounds on benchmark instances
Descrição
Palavras-chave
Capacitated spanning tree, Branch-and-cut, Subproblem optimization
Citação
UCHOA, E. et al. Branch-and-cut and GRASP with hybrid local search for the multi-level capacitated minimum spanning tree problem. In. International Network Optimization Conference (INOC), 2009. Pisa. Anais... Pisa: INOC, 2009. Disponível em: <http://www.di.unipi.it/optimize/Events/proceedings/M/D/2/MD2-2.pdf>. Acesso em: 10 out. 2012.