The expanding equilibrium algorithm

ABSTRACT

Spatial-equilibrium models are the primary framework for applied equilibrium modeling and policy analysis. An effective procedure for solving single commodity problems is described based on a variable dimension, complementary pivoting algorithm of Jones, Saigal, and Schneider. An implementation of this approach called the expanding equilibrium algorithm is described using network data structures and sparse graphs. The data structure that is used presorts the graph to avoid using linked lists while maintaining the flexibility to add arcs to the graph as the algorithm is executing. A computational experiment is developed showing the algorithm's ability to exploit the problem's underlying network and economic structure. Computational results are presented for a computer code written in C and tested on a large-scale, randomly generated problem.

REFERENCES

• 1: COTTLE, R. W., AND DANTZIG, G. B. Complementary pivot theory of mathematical programming. Linear Algebra, Its Applications 1, 1 (Jan. 1968), 103-125.
• 2: DAFERMOS, S., AND SPARROW, F. T. The traffic assignment problem for a general network. j. Res. Nat. Bur. Stand. Sect.-B Math. Sci. 73B, 2 (Apr.-June 1969), 91-117.
• 3: GLASSEY, C. R. A quadratic network optimization model for equilibrium single commodity trade flows. Math. Program. 14, I (Jan. 1978), 98-107.
• 4: HALL, H. H., HEADY, E. O., STOECKER, A., AND SPOSITO, V. A. Spatial equilibrium in U.S. agriculture: A quadratic programming analysis. SIAM Rev. 17, 2 (Apr. 1975), 323-338.
• 5: HOUSE, R. M. USMP regional agricultural programming model: Theoretical and data description. U.S. Dept. of Agriculture, Economic Research Service, 1986.
• 6: P C Jones , R Saigal , M H Schneider, A variable dimension homotopy on networks for computing linear spatial equilibri, Discrete Applied Mathematics, v.13 n.2-3, p.131-156, March. 1986 [doi>10.1016/0166-218X(86)90078-8]
• 7: KING, B. B. What is a SAM? A layman's guide to social account matrices. In Social Accounting Matrices: A Basis for Planning, G. Pyatt and J. J. Round, Eds. The World Bank, Washington, D.C., 1985.
• 8: KLINGMAN, D., NAPIER, A., AND STUTZ, J. NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost for network problems. Manage. Sci. 20, 5 (Jan. 1974), 814-821.
• 9: LEBLANC, L. J., MORLOK, E. K., AND PIERSKALLA, W. P. An efficient approach to solving the road network equilibrium traffic assignment problem. Transport. Res. 6, 5 (Oct. 1975), 309-318.}
• 10: LIN, Y. Y., AND PANG, J. S. Iterative methods for large convex quadratic programs: A survey. School of Management, Univ. of Texas at Dallas, Sept. 1985.
• 11: MCCARL, B. A., AND SPREEN, T. n. Price endogenous mathematical programming as a tool for sector analysis. Am. J. Agric. Econ. 62, 1 (Feb. 1980), 88-102.
• 12: NAGURNEY, A. Computational comparisons of spatial price equilibrium methods. J. Region. Sci. 27, 1 (1987), 55-77.
• 13: PAN(}, J. S. A hybrid method for the solution of some multi-commodity spatial equilibrium problems. Manage. Sci. 27, 10 (Oct. 1981), 1142-1157.
• 14: PANG, J. S., AND LEE, P. S. C. A parametric linear complementarity technique for the computation of equilibrium prices in a single commodity spatial model. Math. Program. 20, 1 (Jan. 1981), 98-107.
• 15: ROCKAFELLAR, R. T. Network Flows and Monotropic Optimization. Wiley, New York, 1984.
• 16: SAIGAL, R. A homotopy for solving large, sparse and structured fixed point problems. Math. Oper. Res. 8, 4 (Nov. 1983), 517-524.
• 17: SAMUELSON, P. Spatial price equilibrium and linear programming. Am. Econ. Rev. 42, 3 (June 1952), 283-303.
• 18: SCHNEIDER, M. H. A complementarity pivoting algorithm for linear network problems. Ann. Oper. Res. 5 (1985/86), 439-462.
• 19: SCHNEIDER, M. H. Single-commodity spatial equilibria: A network complementarity approach. Ph.D. dissertation, Dept. of Industrial Engineering and Management Science, Northwestern University, June 1984.
• 20: TAKAYAMA, T., AND JUDGE, G. G. An interregional activity analysis model of the agricultural sector. J. Farm Econ. 46, 2 (May 1964), 349-365.
• 21: TAKAYAMA, T., AND JUDGE, G. G. Equilibrium among spatially separated markets: A reformulation. Econ. 32, 3 (July 1964), 510-524.
• 22: U.S. DEPARTMENT OF ENERGY. Mathematical structure of the international coal trade model. Office of Coal, Nuclear, Electric and Alternate Fuels, DOE/NBB-0025, Sept. 1982.
• 23: U.S. DEPARTMENT OF ENERGY. Description of the international coal trade model. Office of Coal, Nuclear, Electric and Alternate Fuels, DOE/EI/ll815-1, Sept. 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Performance