Simulated Annealing Algorithm for the Linear Ordering Problem: The Case of Tanzania Input Output Tables

  • Allen R. Mushi Department of Mathematics, University of Dar es Salaam, P. O. Box 35062, Dar es Salaam, Tanzania
Keywords: Combinatorial Optimization; Linear Ordering Problem; Simulated Annealing; Triangulation; Input Output tables

Abstract

Linear Ordering is a problem of ordering the rows and columns of a matrix such that the sum of the upper triangle values is as large as possible. The problem has many applications including aggregation of individual preferences, weighted ancestry relationships and triangulation of input-output tables in economics. As a result, many researchers have been working on the problem which is known to be NP-hard. Consequently, heuristic algorithms have been developed and implemented on benchmark data or specific real-world applications. Simulated Annealing has seldom been used for this problem. Furthermore, only one attempt has been done on the Tanzanian input output table data. This article presents a Simulated Annealing approach to the problem and compares results with previous work on the same data using Great Deluge algorithm. Three cooling schedules are compared, namely linear, geometric and Lundy & Mees. The results show that Simulated Annealing and Great Deluge provide similar results including execution time and final solution quality. It is concluded that Simulated Annealing is a good algorithm for the Linear Ordering problem given a careful selection of required parameters.

Keywords: Combinatorial Optimization; Linear Ordering Problem; Simulated Annealing; Triangulation; Input Output tables

Published
2020-05-27
Section
Articles

Journal Identifiers


eISSN: 2507-7961
print ISSN: 0856-1761