International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 7, No. 7, 8 Jun. 2015
Cover page and Table of Contents: PDF (size: 498KB)
Great Deluge Algorithm for the Linear Ordering Problem: The Case of Tanzanian Input-Output Table
Full Text (PDF, 498KB), PP.28-34
Views: 0 Downloads: 0
Author(s)
Amos Mathias
1,*
Allen R. Mushi
2
Index Terms
Optimization, Linear Ordering, Input-Output Tables, Great Deluge Algorithm
Abstract
Given a weighted complete digraph, the Linear Ordering Problem (LOP) consists of finding and acyclic tournament with maximum weight. It is sometimes referred to as triangulation problem or permutation problem depending on the context of its application. This study introduces an algorithm for LOP and applied for triangulation of Tanzanian Input-Output tables. The algorithm development process uses Great Deluge heuristic method. It is implemented using C++ programming language and tested on a personal computer with 2.40GHZ speed processor. The algorithm has been able to triangulate the Tanzanian input-output tables of size 79×79 within a reasonable time (1.17 seconds). It has been able to order the corresponding economic sectors in the linear order, with upper triangle weight increased from 585,481 to 839,842 giving the degree of linearity of 94.3%.
Cite This Paper
Amos Mathias, Allen R. Mushi, "Great Deluge Algorithm for the Linear Ordering Problem: The Case of Tanzanian Input-Output Table", International Journal of Information Technology and Computer Science(IJITCS), vol.7, no.7, pp.28-34, 2015. DOI:10.5815/ijitcs.2015.07.04
Reference
[1]Mushi Allen Rangia, “The Linear Ordering Problem; An Algorithm for the Optimal Solution”, African Journal of Science and Technology, Vol. 6, pp. 51-64, 2005.
[2]Martí R and Reinelt G, “The Linear Ordering Problem, Exact and Heuristic Methods in Combinatorial Optimization”, Springer, Applied Mathematical Sciences, 2011.
[3]Schiavinotto T and Stüzle T, “The Linear Ordering Problem, Instances, Search Space Analysis and Algorithms”, Journal of Mathematical Modelling and Algorithms, Vol. 3, pp. 367-402, 2004.
[4]Chenery BH and Watanable T, “International Comparisons of the Structure of Production”, Econometrica, Vol. 26, pp. 4, 1958.
[5]Grötschel M, Jünger M and Reinelt G, “A Cutting Plane Algorithm for the Linear Ordering Problem”, Operation Research Society of America, Vol. 32, pp. 3206-1195, 1984.
[6]Tromble WR, “Search and Learning for the Linear Ordering Problem with an Application to Machine translation”, Johns Hopkins University, USA (PhD thesis), 2009.
[7]Martí, Reinelt and Duarte, “Linear Ordering Problem”, Optsicom Project: http://www.optsicom.es/lolib/, June 2014.
[8]Chana S, Kobylański P, 1996, “A New Heuristic Algorithm Solving the Linear Ordering Problem”. Kluwer Academic Publishers, Vol. 6, pp. 191-205, 1996.
[9]Garcia C, Pérez-Brito D, Campos V and Martí R, 2005, “Variable Neighborhood Search for the linear ordering problem”, Elsevier Science Ltd, Vol.33, pp. 3549–3565, 2006.
[10]Campos V, Glover F, Laguna M and Martí R, “An Experimental Evaluation of Scatter Search for Linear Ordering Problem”, Journal of Global Optimization, Vol. 21, pp. 397-414, 2001.
[11]Celso S. Sakuraba, Mutsunori Yagiura, “Efficient Local Search Algorithms for the Linear Ordering Problem”, International Transactions in Operational Research, Vol. 17, pp 711-737, 2010.
[12]Tao Y., Wang T, Lu Z., Hao J., “A Multi-Parent Memetic Algorithm for the Linear Ordering Problem”, arxiv.org/abs/1405.4507v1 [cs.NE] (Submitted to arXiv on 18, May 2014).
[13]Doeck G, “New Optimization Heuristics, The Great Deluge Algorithm and The Record-to-Record Travel”, Heidelberg Scientific Centre, Vol. 104, pp. 86-92, 1993.
[14]Mushi Allen Rangia, “Two-Phase Great Deluge Algorithm for Course Timetabling problem”, International Journal of Advanced Research in Computer Science, Vol. 2, No.5, pp. 73-83, 2011.
[15]Mushi Allen Rangia, “Non-Linear Great Deluge algorithm for Tanzanian High Schools Timetabling”, International Journal of Advanced Research in Computer Science, Vol. 2, No. 4, pp.584-590, 2011.
[16]Landa-Silva D and Obit J, “Great Deluge with Non-linear Decay Rate for Solving Course Timetabling Problems”, Intelligent Systems, Vol. 1, pp. 8–18, 2008.
[17]Turabieh H, Abdullah S and McCollum B, “Electromagnetism-like Mechanism with Force Decay Rate Great Deluge for the Course Timetabling Problem”, Springer, UK, 2009.
[18]McMullan P and McCollum B, “Dynamic Job Scheduling on Grid Environment Using Great Deluge Algorithm”, Berlin Heidelberg, Springer, Vol. 4671, pp. 283–292, 2007.
[19]Lamel J., Richter J., Teufelsbauer W., “Patterns of industrial structure and economic development: Triangulation of input-output tables of ECE countries”, European Economic Review, Vol. 3, No. 1, pp 47–63, 1972.
[20]Burke E., Yuri b., Newall J., Petrovic, S., “A Time Predefined Local Search Approach to Exam Timetabling Problems”, IIE Transactions of Operations Engineering, Vol. 36 pp 509-528, 2004.
[21]National Bureau of Statistics, “Input-Output Table of Tanzania for 1992”, Input-output table construction project, supported by Sida through Statistics Sweden Vol. 2, 1992.
[22]Leontief, Wassily, “Input-Output Economics”, Oxford University Press, New York, USA, 1986.