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 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.