Optimization Online


Lower Bounds for the Quadratic Minimum Spanning Tree Problem Based on Reduced Cost Computation

Borzou Rostami(bo.rostami***at***gmail.com)
Federico Malucelli(federico.malucelli***at***polimi.it)

Abstract: The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MST whose cost considers also the interaction between every pair of edges of the tree. In this paper we review different strategies found in the literature to compute a lower bound for the QMSTP and develop new bounds based on a reformulation scheme and some new mixed 0-1 linear formulations that result from a reformulationlinearization technique (RLT). The new bounds take advantage of an efficient way to retrive dual information from the MSTP reduced cost computation. We compare the new bounds with the other bounding procedures in terms of both overall strength and computational effort. Computational experiments indicate that the dual-ascent procedure applied to the new RLT formulation provides the best bounds at the price of increased computational effort, while the bound obtained using the reformulation scheme seems to tradeoff between the bound tightness and computational effort.

Keywords: Quadratic minimum spanning tree problem, Lagrangian relaxation, Reformulation-linearization technique, Lower bound, Dual-ascent approach, Reduced costs

Category 1: Combinatorial Optimization

Category 2: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 09/23/2014
Entry Accepted: 09/23/2014
Entry Last Modified: 09/23/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society