DECEA - Trabalhos apresentados em eventos

URI permanente para esta coleçãohttp://www.hml.repositorio.ufop.br/handle/123456789/555

Navegar

Filtros

20091

Configurações

Data final: 2009Assunto: search.filters.subject.Capacitated spanning tree

Resultados da Pesquisa

Agora exibindo 1 - 1 de 1
  • Nenhuma Miniatura Disponível
    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 Xavier
    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