Use este identificador para citar ou linkar para este item: http://repositorio.ufla.br/jspui/handle/1/42454
Registro completo de metadados
Campo DCValorIdioma
dc.creatorGuimarães, Dilson Almeida-
dc.creatorCunha, Alexandre Salles da-
dc.creatorPereira, Dilson Lucas-
dc.date.accessioned2020-08-17T18:51:00Z-
dc.date.available2020-08-17T18:51:00Z-
dc.date.issued2020-01-
dc.identifier.citationGUIMARÃES, D. A.; CUNHA, A. S. da; PEREIRA, D. L. Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem. European Journal of Operational Research, [S. I.], v. 280, p. 46-58, Jan. 2020.pt_BR
dc.identifier.urihttps://doi.org/10.1016/j.ejor.2019.07.038pt_BR
dc.identifier.urihttp://repositorio.ufla.br/jspui/handle/1/42454-
dc.description.abstractIn this paper, we investigate Semidefinite Programming (SDP) lower bounds for the Quadratic Minimum Spanning Tree Problem (QMSTP). Two SDP lower bounding approaches are introduced here. Both apply Lagrangian Relaxation to an SDP relaxation for the problem. The first one explicitly dualizes the semidefiniteness constraint, attaching to it a positive semidefinite matrix of Lagrangian multipliers. The second relies on a semi-infinite reformulation for the cone of positive semidefinite matrices and dualizes a dynamically updated finite set of inequalities that approximate the cone. These lower bounding procedures are the core ingredient of two QMSTP Branch-and-bound algorithms. Our computational experiments indicate that the SDP bounds computed here are very strong, being able to close at least 70% of the gaps of the most competitive formulation in the literature. As a result, their accompanying Branch-and-bound algorithms are competitive with the best previously available QMSTP exact algorithm in the literature. In fact, one of these new Branch-and-bound algorithms stands out as the new best exact solution approach for the problem.pt_BR
dc.languageenpt_BR
dc.publisherElsevierpt_BR
dc.rightsrestrictAccesspt_BR
dc.sourceEuropean Journal of Operational Researchpt_BR
dc.subjectCombinatorial optimizationpt_BR
dc.subjectSpanning treespt_BR
dc.subjectLagrangian relaxationpt_BR
dc.subjectSemidefinite programmingpt_BR
dc.subjectSemi-infinite programmingpt_BR
dc.subjectProgramação semidefinidapt_BR
dc.subjectÁrvore geradora mínima quadráticapt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectRelaxação lagrangeanapt_BR
dc.subjectÁrvore de extensãopt_BR
dc.subjectProgramação semi-infinitapt_BR
dc.titleSemidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problempt_BR
dc.typeArtigopt_BR
Aparece nas coleções:DCC - Artigos publicados em periódicos

Arquivos associados a este item:
Não existem arquivos associados a este item.


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.

Ferramentas do administrador