Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem

DOI10.1016/j.ejor.2019.07.038zbMath1430.90473OpenAlexW2963214284MaRDI QIDQ2272297

Dilson Almeida Guimarães, Dilson Lucas Pereira, Alexandre Salles da Cunha

Publication date: 9 September 2019

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2019.07.038

zbMATH Keywords

Lagrangian relaxationsemidefinite programmingcombinatorial optimizationsemi-infinite programmingspanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items (2)

A Branch-and-Bound Algorithm for Team Formation on Social Networks ⋮ Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem

Uses Software

• LAPACK
• Gurobi
• PLCP
• SQPlab

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• Solving the quadratic minimum spanning tree problem
• Combinatorial optimization with one quadratic term: spanning trees and forests
• Polyhedral and semidefinite programming methods in combinatorial optimization
• Non delayed relax-and-cut algorithms
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• The quadratic minimum spanning tree problem and its variations
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• Linear semi-infinite programming theory: an updated survey
• Branching rules revisited
• Complete description for the spanning tree problem with one linearised quadratic term
• The Quadratic Assignment Problem
• Assignment Problems and the Location of Economic Activities
• Tabu Search Algorithm Based on Strategic Oscillation for Nonlinear Minimum Spanning Tree Problems
• LAPACK Users' Guide
• Cones of Matrices and Set-Functions and 0–1 Optimization
• A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
• An Algorithm for Constrained Optimization with Semismooth Functions
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Primal--Dual Path-Following Algorithms for Semidefinite Programming
• A Spectral Bundle Method for Semidefinite Programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Validation of subgradient optimization
• An Interior-Point Method for Semidefinite Programming
• Polyhedral results, branch‐and‐cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem
• Matroids and the greedy algorithm
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• Numerical optimization. Theoretical and practical aspects. Transl. from the French
• On The Boolean Quadric Forest Polytope

This page was built for publication: Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem