A NEW ALGORITHM FOR THE TRIANGULATION OF INPUT–OUTPUT TABLES IN ECONOMICS

B. H. Chiarini, W. Chaovalitwongse and P. M. Pardalos
Additional contact information
B. H. Chiarini: Center for Applied Optimization, Dept. of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, P.O. Box 116595, Gainesville, FL 32611, USA
W. Chaovalitwongse: Center for Applied Optimization, Dept. of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, P.O. Box 116595, Gainesville, FL 32611, USA
P. M. Pardalos: Center for Applied Optimization, Dept. of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, P.O. Box 116595, Gainesville, FL 32611, USA

Chapter 15 in Supply Chain and Finance, 2004, pp 253-272 from World Scientific Publishing Co. Pte. Ltd.

Abstract: AbstractDeveloped by Leontief in the 1930s, input-output models have become an indispensable tool for economists and policy-makers. They provide a framework upon which researchers can systematically analyze the interrelations among the sectors of an economy. In an input-output model, a table is constructed where each entry represents the flow of goods between each pair of sectors. Special features of the structure of this matrix are revealed by a technique called triangulation. It is shown to be equivalent to the linear ordering problem (LOP), which is an $\mathcal{NP}$-hard combinatorial optimization problem. Due to its complexity, it is essential in practice to search for quick approximate (heuristic) algorithms for the linear ordering problem. In addition to the triangulation of input-output tables, the LOP has a wide range of applications in practice. In this chapter, we develop a new heuristic procedure to find high quality solutions for the LOP. The proposed algorithm is based on a Greedy Randomized Adaptive Search Procedure (GRASP), which is one of the most effective heuristics for solving combinatorial and global optimization problems to date. We propose an improved solution technique by using a new local search scheme and integrating a path-relinking procedure for intensification. We tested our implementation on the set of 49 real-world instances of input-output tables in LOLIB22. In addition, we tested a set of 30 large randomly-generated instances due to Mitchell.18 Most of the LOLIB instances were solved to optimality within 0.87 seconds on average. The average gap for the Mitchell instances was 0.0173% with an average running time of 21.98 seconds. The results prove the efficiency and high-quality of the algorithm.

Keywords: Finance; Supply Chain; E-Commerce; Optimization; Mathematical Modeling; Operations Research (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.worldscientific.com/doi/pdf/10.1142/9789812562586_0015 (application/pdf)
https://www.worldscientific.com/doi/abs/10.1142/9789812562586_0015 (text/html)
Ebook Access is available upon purchase.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:wschap:9789812562586_0015

Ordering information: This item can be ordered from

Access Statistics for this chapter

More chapters in World Scientific Book Chapters from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().