Use este identificador para citar ou linkar para este item: http://repositorio.ufla.br/jspui/handle/1/42453
Registro completo de metadados
Campo DCValorIdioma
dc.creatorPereira, Dilson Lucas-
dc.creatorCunha, Alexandre Salles da-
dc.date.accessioned2020-08-17T18:47:31Z-
dc.date.available2020-08-17T18:47:31Z-
dc.date.issued2020-07-
dc.identifier.citationPEREIRA, D. L., CUNHA, A. S. da. Dynamic intersection of multiple implicit Dantzig–Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem. European Journal of Operational Research, [S. I.], v. 284, n. 2, p. 413-426, July 2020. DOI: https://doi.org/10.1016/j.ejor.2019.12.042.pt_BR
dc.identifier.urihttps://doi.org/10.1016/j.ejor.2019.12.042pt_BR
dc.identifier.urihttp://repositorio.ufla.br/jspui/handle/1/42453-
dc.description.abstractIn this paper, we introduce a dynamic Dantzig–Wolfe (DW) reformulation framework for the Adjacent Only Quadratic Minimum Spanning Tree Problem (AQMSTP). The approach is dynamic in the sense that the structures over which the DW reformulation takes place are defined on the fly and not beforehand. The idea is to dynamically convexify multiple promising regions of the domain, without explicitly formulating DW master programs over extended variable spaces and applying column generation. Instead, we use the halfspace representation of polytopes as an alternative to mathematically represent the convexified region in the original space of variables. Thus, the numerical machinery we devise for computing AQMSTP lower bounds operates in a cutting plane setting, separating projection cuts associated to the projection of the variables used in the extended DW reformulations. Our numerical experience indicates that the bounds are quite strong and the computational times are mostly spent by linear programming reoptimization and not by the separation procedures. Thus, we introduce a Lagrangian Relax-and-cut algorithm for approximating these bounds. The method is embedded in a Branch-and-Bound algorithm for the AQMSTP. Although it does not strictly dominate the previous state-of-the-art exact method, it is able to solve more instances to proven optimality and is significantly faster for the hardest AQMSTP instances in the literature.pt_BR
dc.languageenpt_BR
dc.publisherElsevierpt_BR
dc.rightsrestrictAccesspt_BR
dc.sourceEuropean Journal of Operational Researchpt_BR
dc.subjectCombinatorial optimizationpt_BR
dc.subjectDantzig–Wolfe decompositionpt_BR
dc.subjectCutting planespt_BR
dc.subjectLagrangian relaxationpt_BR
dc.subjectSpanning treespt_BR
dc.subjectCombinatorial optimizationpt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectDecomposição de Dantzig-Wolfept_BR
dc.subjectMétodo de planos de cortept_BR
dc.subjectRelaxação Lagrangeanapt_BR
dc.subjectÁrvore de extensãopt_BR
dc.subjectÁrvore geradora mínima quadráticapt_BR
dc.titleDynamic intersection of multiple implicit Dantzig–Wolfe decompositions applied to the adjacent only 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