Intensification and diversification with elite tabu search solutions for the linear ordering problem

Intensification and diversification with elite tabu search solutions for the linear ordering problem

0.00 Avg rating0 Votes
Article ID: iaor20002311
Country: United Kingdom
Volume: 26
Issue: 12
Start Page Number: 1217
End Page Number: 1230
Publication Date: Oct 1999
Journal: Computers and Operations Research
Authors: , ,
Keywords: economics
Abstract:

In this paper, we develop a new heuristic procedure for the linear ordering problem (LOP). This NP-hard problem has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input–output tables in economics. In this paper, we concentrate on matrices that arise in the context of this real-world application. The proposed algorithm is based on the tabu search methodology and incorporates strategies for search intensification and diversification. For search intensification, we experiment with path relinking, a strategy proposed several years ago in connection with tabu search, which has been rarely used in actual implementations. Extensive computational experiments with input–output tables show that the proposed procedure outperforms the best heuristics reported in the literature. Furthermore, the experiments also show the merit of achieving a balance between intensification and diversification in the search.

Reviews

Required fields are marked *. Your email address will not be published.