IDEAS home Printed from https://ideas.repec.org/h/wsi/wschap/9789812562586_0015.html
   My bibliography  Save this book chapter

A New Algorithm For The Triangulation Of Input–Output Tables In Economics

In: Supply Chain And Finance

Author

Listed:
  • 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)

Abstract

Developed 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.

Suggested Citation

  • B. H. Chiarini & W. Chaovalitwongse & P. M. Pardalos, 2004. "A New Algorithm For The Triangulation Of Input–Output Tables In Economics," World Scientific Book Chapters, in: Panos M Pardalos & Athanasios Migdalas & George Baourakis (ed.), Supply Chain And Finance, chapter 15, pages 253-272, World Scientific Publishing Co. Pte. Ltd..
  • Handle: RePEc:wsi:wschap:9789812562586_0015
    as

    Download full text from publisher

    File URL: https://www.worldscientific.com/doi/pdf/10.1142/9789812562586_0015
    Download Restriction: Ebook Access is available upon purchase.

    File URL: https://www.worldscientific.com/doi/abs/10.1142/9789812562586_0015
    Download Restriction: Ebook Access is available upon purchase.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dietzenbacher, Erik & Yan, Bingqian, 2024. "Explaining the direction of emissions embodied in trade from hypotheses based on country rankings11Funding information: Bingqian Yan received financial support from the National Natural Science Founda," Energy Economics, Elsevier, vol. 129(C).
    2. Keisuke Nansai & Shigemi Kagawa & Yasushi Kondo & Sangwon Suh & Rokuta Inaba & Kenichi Nakajima, 2009. "Improving The Completeness Of Product Carbon Footprints Using A Global Link Input-Output Model: The Case Of Japan," Economic Systems Research, Taylor & Francis Journals, vol. 21(3), pages 267-290.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:wschap:9789812562586_0015. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscientific.com/page/worldscibooks .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.