Hybrid Metaheuristic Algorithm for the Linear Ordering Problem: The Case of Tanzanian Input-Output Tables

Abstract

Linear Ordering is the problem of finding an acyclic tournament in a complete directed weighted graph that maximizes the sum of the arc weights. This is equivalent to finding an order of elements of a matrix associated with a complete weighted digraph in such a way that the sum of the entries in the upper triangle is as large as possible. The problem has interesting applications, including the
triangulation of input-output tables in economics. Linear Ordering has been proven to be NP-Hard and therefore, no polynomial time algorithm is known for its solution. Metaheuristic techniques have been applied with reported success in many instances, including instances of real-world problems. This paper presents a hybrid metaheuristic algorithm that combines Flex Deluge and Simulated Annealing in an attempt to find a near-optimal solution to the linear ordering problem. Tanzanian input-output tables are used as a case study. The results are compared with the performances of Simulated Annealing, Great Deluge, and Flex Deluge algorithms. It is concluded that the new procedure is good for the linear ordering problem with comparable performance in terms of solution quality and better performance in terms of time by 26%.

Keywords: Combinatorial Optimization, Input-output tables, Triangulation, Great Deluge Algorithm, Global heuristics