Use este identificador para citar ou linkar para este item:
http://www.repositorio.ufop.br/jspui/handle/123456789/7176
Título: | Branch-and-cut and hybrid local search for themulti-level capacitated minimum spanning tree problem. |
Autor(es): | Uchoa, Eduardo Toffolo, Túlio Ângelo Machado Souza, Maurício Cardoso de Martins, Alexandre Xavier Fukasawa, Ricardo |
Palavras-chave: | Network design Fenchel cuts |
Data do documento: | 2012 |
Referência: | UCHOA, E. et al. Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem. Networks, New York, v. 59, n. 1, p. 148-160, jan. 2012. Disponível em: <http://onlinelibrary.wiley.com/doi/10.1002/net.20485/epdf>. Acesso em: 23 jan. 2017. |
Resumo: | 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. |
URI: | http://www.repositorio.ufop.br/handle/123456789/7176 |
Link para o artigo: | http://onlinelibrary.wiley.com/doi/10.1002/net.20485/epdf |
DOI: | https://doi.org/10.1002/net.20485 |
ISSN: | 1097-0037 |
Aparece nas coleções: | DECOM - Artigos publicados em periódicos |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
ARTIGO_BranchCutHybrid.pdf Until 2030-01-23 | 129,45 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.