Supply Chain And Finance: Series on Computers and Operations Research, Vol. 2

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