Please use this identifier to cite or link to this item:
metadata.artigo.dc.title: Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem
metadata.artigo.dc.creator: Guimarães, Dilson Almeida
Cunha, Alexandre Salles da
Pereira, Dilson Lucas
metadata.artigo.dc.subject: Combinatorial optimization
Spanning trees
Lagrangian relaxation
Semidefinite programming
Semi-infinite programming
Programação semidefinida
Árvore geradora mínima quadrática
Otimização combinatória
Relaxação lagrangeana
Árvore de extensão
Programação semi-infinita
metadata.artigo.dc.publisher: Elsevier Jan-2020
metadata.artigo.dc.identifier.citation: GUIMARÃ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.
metadata.artigo.dc.description.abstract: In 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.
metadata.artigo.dc.language: en
Appears in Collections:DCC - Artigos publicados em periódicos

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.