Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation

DOI10.1016/j.cor.2015.06.005zbMath1349.90721OpenAlexW569517619MaRDI QIDQ342082

Federico Malucelli, Borzou Rostami

Publication date: 17 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2015.06.005

zbMATH Keywords

Lagrangian relaxationlower boundreformulation-linearization techniquedual-ascent approachquadratic minimum spanning tree problemreduced costs

Mathematics Subject Classification ID

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

Related Items

Lower bounding procedure for the asymmetric quadratic traveling salesman problem, The quadratic cycle cover problem: special cases and efficient bounds, Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem, A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs, A characterization of linearizable instances of the quadratic minimum spanning tree problem, The quadratic shortest path problem: complexity, approximability, and solution methods, Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem, The linearization problem of a binary quadratic problem and its applications, Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
• Solving the quadratic minimum spanning tree problem
• Combinatorial optimization with one quadratic term: spanning trees and forests
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• A revised reformulation-linearization technique for the quadratic assignment problem
• Constrained 0-1 quadratic programming: basic approaches and extensions
• Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
• The Quadratic Assignment Problem
• A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• A New Lower Bound for the Quadratic Assignment Problem
• Exact Solution of the Quadratic Knapsack Problem
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• On The Boolean Quadric Forest Polytope