Branch-and-cut and hybrid local search for themulti-level capacitated minimum spanning tree problem.

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.creatorUchoa, Eduardo-
Autor(es): dc.creatorToffolo, Túlio Ângelo Machado-
Autor(es): dc.creatorSouza, Maurício Cardoso de-
Autor(es): dc.creatorMartins, Alexandre Xavier-
Autor(es): dc.creatorFukasawa, Ricardo-
Data de aceite: dc.date.accessioned2025-08-21T15:56:01Z-
Data de disponibilização: dc.date.available2025-08-21T15:56:01Z-
Data de envio: dc.date.issued2017-02-01-
Data de envio: dc.date.issued2017-02-01-
Data de envio: dc.date.issued2012-
Fonte completa do material: dc.identifierhttp://www.repositorio.ufop.br/handle/123456789/7176-
Fonte completa do material: dc.identifierhttp://onlinelibrary.wiley.com/doi/10.1002/net.20485/epdf-
Fonte completa do material: dc.identifierhttps://doi.org/10.1002/net.20485-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1027845-
Descrição: dc.descriptionWe 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsaberto-
Palavras-chave: dc.subjectNetwork design-
Palavras-chave: dc.subjectFenchel cuts-
Título: dc.titleBranch-and-cut and hybrid local search for themulti-level capacitated minimum spanning tree problem.-
Aparece nas coleções:Repositório Institucional - UFOP

Não existem arquivos associados a este item.