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

In this paper, we develop a new heuristic procedure for the linear ordering problem (LOP). This NP-hard problem has a significant number of applicatio ns in practice. The LOP, for example, is equivalent to the so-called triang ulation problem for input-output tables in economics; In this paper, we con centrate on matrices that arise in the context of this real-world applicati on. The proposed algorithm is based on the tabu search methodology and inco rporates strategies for search intensification and diversification. For sea rch intensification, we experiment with path relinking, a strategy proposed several years ago in connection with tabu search, which has been rarely us ed in actual implementations. Extensive computational experiments with inpu t-output tables show that the proposed procedure outperforms the best heuri stics reported in the literature. Furthermore, the experiments also show th e merit of achieving a balance between intensification and diversification in the search.