An efficient tabu search algorithm for the linear ordering problem

Abstract

Given a directed graph with n vertices, m edges and costs on the edges, the linear ordering problem (LOP) consists of finding a permutation of the vertices so that the total cost of the reverse edges is minimized, where an edge is called a reverse edge if its head vertex is at a position before the tail in the permutation. Known as an NP-hard problem, the LOP has a number of real-world applications such as the analysis of data called industry transaction table or input-output matrix (I/O table) in the field of economy. In this paper, we propose an algorithm based on tabu search for the LOP. We generalize an algorithm called TREE, which was proposed to search for a best solution in the neighborhood efficiently, so that the new algorithm can be incorporated in the tabu search algorithm and can search for a non-tabu best solution in the neighborhood efficiently. Our algorithm also features an adaptive control mechanism of the tabu tenure by using a cycling-detection mechanism based on a probabilistic analysis. Finally, we compare the experimental results of the proposed algorithm with those of an existing iterated local search algorithm (ILS). The proposed algorithm obtained better results than the ILS for many instances.

Keywords

• heuristic algorithm
• linear ordering problem
• tabu search
• local search
• tabu tenure