Tabu search with strategic oscillation for the quadratic minimum spanning tree

Manuel Lozano, Fred Glover, Carlos García-Martínez, Francisco Rodríguez and Rafael Martí

IISE Transactions, 2014, vol. 46, issue 4, 414-428

Abstract: The quadratic minimum spanning tree problem consists of determining a spanning tree that minimizes the sum of costs of the edges and pairs of edges in the tree. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated metaheuristics. This article presents a simple Tabu Search (TS) for this problem that incorporates Strategic Oscillation (SO) by alternating between constructive and destructive phases. The commonalties shared by this strategy and the more recently introduced methodology called iterated greedy search are shown and implications of their differences regarding the use of memory structures are identified. Extensive computational experiments reveal that the proposed SO algorithm with embedded TS is highly effective for solving complex instances of the problem as compared with the best metaheuristics in the literature. A hybrid method that proves similarly effective for problem instances that are both simple and complex is introduced.

Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2013.768785 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:46:y:2014:i:4:p:414-428

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2013.768785

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().