Navegando por Autor "Fukasawa, Ricardo"

Filtrar resultados informando as primeiras letras
Agora exibindo 1 - 1 de 1
  • Imagem de Miniatura
    Item
    Branch-and-cut and hybrid local search for themulti-level capacitated minimum spanning tree problem.
    (2012) Uchoa, Eduardo; Toffolo, Túlio Ângelo Machado; Souza, Maurício Cardoso de; Martins, Alexandre Xavier; Fukasawa, Ricardo
    We propose algorithms to compute tight lower boundsand high quality upper bounds (UBs) for the multilevelcapacitated minimum spanning tree problem. We firstdevelop a branch-and-cut algorithm, introducing somenew features: (i) the exact separation of cuts correspond-ing to some master equality polyhedra found in theformulation; (ii) the separation of Fenchel cuts, solvingLPs considering all the possible solutions restricted tosmall portions of the graph. We then use that branch-and-cut within a GRASP that performs moves by solvingto optimality subproblems corresponding to partial solu-tions. The computational experiments were conductedon 450 benchmark instances from the literature. Numer-ical results show improved best known (UBs) for almostall instances that could not be solved to optimality.