
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.creator | Pereira, Dilson Lucas | - |
| Autor(es): dc.creator | Cunha, Alexandre Salles da | - |
| Data de aceite: dc.date.accessioned | 2026-02-09T12:34:40Z | - |
| Data de disponibilização: dc.date.available | 2026-02-09T12:34:40Z | - |
| Data de envio: dc.date.issued | 2020-08-17 | - |
| Data de envio: dc.date.issued | 2020-08-17 | - |
| Data de envio: dc.date.issued | 2020-07 | - |
| Fonte completa do material: dc.identifier | https://repositorio.ufla.br/handle/1/42453 | - |
| Fonte completa do material: dc.identifier | https://doi.org/10.1016/j.ejor.2019.12.042 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1164098 | - |
| Descrição: dc.description | In 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. | - |
| Idioma: dc.language | en | - |
| Publicador: dc.publisher | Elsevier | - |
| Direitos: dc.rights | restrictAccess | - |
| ???dc.source???: dc.source | European Journal of Operational Research | - |
| Palavras-chave: dc.subject | Combinatorial optimization | - |
| Palavras-chave: dc.subject | Dantzig–Wolfe decomposition | - |
| Palavras-chave: dc.subject | Cutting planes | - |
| Palavras-chave: dc.subject | Lagrangian relaxation | - |
| Palavras-chave: dc.subject | Spanning trees | - |
| Palavras-chave: dc.subject | Combinatorial optimization | - |
| Palavras-chave: dc.subject | Otimização combinatória | - |
| Palavras-chave: dc.subject | Decomposição de Dantzig-Wolfe | - |
| Palavras-chave: dc.subject | Método de planos de corte | - |
| Palavras-chave: dc.subject | Relaxação Lagrangeana | - |
| Palavras-chave: dc.subject | Árvore de extensão | - |
| Palavras-chave: dc.subject | Árvore geradora mínima quadrática | - |
| Título: dc.title | Dynamic intersection of multiple implicit Dantzig–Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem | - |
| Tipo de arquivo: dc.type | Artigo | - |
| Aparece nas coleções: | Repositório Institucional da Universidade Federal de Lavras (RIUFLA) | |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: