DECEA - Trabalhos apresentados em eventos
URI permanente para esta coleçãohttp://www.hml.repositorio.ufop.br/handle/123456789/555
Navegar
Item Branch-and-cut and GRASP with hybrid local search for the multi-level capacitated minimum spanning tree problem.(2009) Uchoa, Eduardo; Toffolo, Túlio Ângelo Machado; Souza, Maurício Cardoso de; Martins, Alexandre XavierWe 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