Browsing by Author "Mathias, Amos"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Development of an algorithm for the linear ordering problem using great deluge heuristic:a case of Tanzania input-output tables.
    (University of Dar es Salaam, 2014) Mathias, Amos
    The Linear Ordering Problem (LOP) falls under the class of Non-deterministic Polynomial time hard Combinatorial Optimization problems. This problem is sometimes referred to as triangulation problem or permutation problem depending on the context in which it is used. The problem is applicable in triangulation of Input-Output (I/O) tables, archaeological seriation, minimizing total weighted completion time in one-machine scheduling, ordering of teams in sports tournaments, machine translation as well as aggregation of individual preferences.LOP has been a problem of interest to many researchers to date. It has therefore received considerable attention where a number of algorithms for its solution search have been developed. This study introduces a new algorithm for solving the LOP particularly for a triangulation problem. The algorithm development process uses Great Deluge heuristic methods with consideration of graph theoretical interpretation of the problem. The method has not been applied to LOP to the best of our knowledge. The algorithm code is implemented on a C++ programming language and tested on the personal computer with 2.40GHZ speed processor.The developed algorithm (GDA_LOP) has been able to triangulate (79,79) Tanzanian I/O tables collected from Tanzania National Bureau of Statistics (OfisiyaTaifayaTakwimu (TOTT)) within a reasonable time scale. It has also been able to order the corresponding economic sectors in the linear order, with upper triangle weight increased from 585,481 to 839,842 million shillings.