We have applied parallel and serial variational inequality (VI) diagonal decomposition algorithms to large-scale, multicommodity market equilibrium problems. These decomposition algorithms resolve the VI problems into single commodity problems, which are then solved as quadratic programming problems. The algorithms are implemented on an IBM 3090-600E, and randomly gen erated linear and nonlinear problems with as many as 100 markets and 12 commodities are solved. The com putational results demonstrate that the parallel diagonal decomposition scheme is amenable to paralielization. This is the first time that multicommodity equilibrium problems of this scale and level of generality have been solved. Furthermore, this is the first study to compare the efficiencies of parallel and serial VI decomposition algorithms. Although we have selected as a prototype an equilibrium problem in economics, virtually any equilibrium problem can be formulated and studied as a variational inequality problem. Hence, our results are not limited to applications in economics and operations research.
Get full access to this article
View all access options for this article.
References
1.
Aashtiani, M.Z., and Magnanti, T.L.1981. Equilibria on a congested transportation network. SIAM J. Algebraic Discrete Methods2:213-226.
2.
Aashtiani, M.Z., and Magnanti, T.L.1982. A linearization and decomposition algorithm for computing urban traffic equilibria. In Proceedings of the 1982 IEEE international large scale systems symposium, pp. 8-19.
3.
Beckmann, M.J., McGuire, C.B., and Winsten, C.B.1956. Studies in the economics of transportation. New Haven, Conn.: Yale University Press.
4.
Bertsekas, D.P., and Gafni, E.1982. Projection methods for variational inequalities and application to the traffic assignment problem. Math. Programming Stud.17:139-159.
5.
Border, K.C.1985. Fixed point theorems with applications to economics and game theory. Cambridge, U.K.: Cambridge University Press .
6.
Carey, M.1977. Integrability and mathematical programming models: a survey and parametric approach. Econometrica45:1957-1976.
7.
Cottle, R.V.1974. Complementarity and variational inequality problems. Symposia Mathematica19:59-70.
8.
Dafermos, S.1972. The traffic assignment problem for multiclass-user transportation networks. Transportation Science6:73-87.
9.
Dafermos, S.1980. Traffic equilibrium and variational inequalities. Transportation Science14:42-54.
10.
Dafermos, S.1982. The general multimodal network equilibrium problem with elastic demand. Networks12:57-72.
11.
Dafermos, S.1983. An iterative scheme for variational inequalities. Math. Programming28:57-72.
Dafermos, S.1986b. Isomorphic multiclass spatial price and multimodal traffic network equilibrium models. Regional Science and Urban Econmnics16:197-209.
14.
Dafermos, S.1987. Congested transportation networks and variational inequalities . In Flow control of congested networks (NATO ASI series, series F: computer and systems sciences, vol. 38, edited by Odoni, Bianco, and Szego.New York: Springer-Verlag.
15.
Dafermos, S., and McKelvey, S.C.1986. Equilibrium analysis of competitive economic systems and variational inequalities. LCDS/CCS #86-26. Brown University , Division of Applied Mathematics.
16.
Dafermos, S., and Nagumey, A.1984. Stability and sensitivity analysis for a combined network equilibrium model. In Proceedings of the ninth international symposium on transportation and traffic, edited by W. J. Volmuller and R. Hamerslag. Utrecht, The Netherlands: VNU Press, pp. 217-231.
17.
Dafermos, S., and Nagumey, A.1987. Supply and demand equilibration algorithms for a class of market equilibrium problems. Transportation Science, in press.
18.
Eydeland, A., and Nagurney, A.1988. Analysis of progressive equilibration algorithms: the case of linear transaction costs. University of Massachusetts , Amherst, School of Management .
19.
Florian, M., and Los, M.1982. A new look at static spatial price equilibrium models. Regioaxal Science andUrban Economics12:579-597.
20.
Florian, M., and Spiess, H.1982. The convergence of diagonalization algorithms for asymmetric network equilibrium problems. Transportation Science16B:477-483.
21.
Friesz, T.L., Tobin, R.L., Smith, T.E., and Harker, P.T.1983. A nonlinear complementarity formulation and solution procedure for the general derived demand network equilibrium problem. J. RegionalScience23:337-359.
22.
Gabay, D., and Moulin, H.1980. On the uniqueness and stability of Nash equilibria in noncooperative games. In Applied stochastic control of econometrics and management science, edited by Bensoussan, Kleindorf, and Tapiero.Amsterdam: North-Holland.
23.
Hartman, P., and Stampacchia, G.1966. On some nonlinear elliptic differential functional equations . Acta Math.115:271-310.
24.
IBM Corporation. 1988. Parallel FORTRAN Language and Library Reference. Document No. SC23-0431-0.
25.
Kinderlehrer, D., and Stampacchia, G.1980. An introduction to variational inequalities. New York: Academic Press.
26.
Lemke, C.E.1980. A survey of complementarity theory. In Variational inequalities and complementarity problems, chapter 15, edited by Cottle, Giannessi, and Lions.New York: Wiley.
27.
Magnanti, T.1984. Models and algorithms for predicting urban traffic equilibrium . In Transportation planning models, edited by M. Florian.Amsterdam: North-Holland.
28.
Mahmassani, H.S., and Mouskos, K.C.1988. Some numerical results on the diagonahzation algorithm for network assignment with asymmetric interactions between cars and trucks . Transportation Research22B:275-290.
29.
Mathiesen, L.1985. Computational experience in solving equilibrium models by a sequence of linear complementarity problems. Operations Research33:1225-1250.
Nagurney, A.1986. Computational comparisons of algorithms for general asymmetric traffic equilibrium problems with fixed and elastic demands. Transportation Research20B:78-84.
32.
Nagurney, A.1987a. Competitive equilibrium problems, variational inequalities, and regional science. J. RegionalScience27:503-517.
33.
Nagurney, A.1987b. Computational comparisons of spatial price equilibrium methods. J. RegionalScience27:55-76.
34.
Nagurney, A.1988a. Algorithms for oligopolistic market equilibrium problems . Regional Science and Urban Economics, 18:425-445.
35.
Nagurney, A.1988b. Import and export equilibration algorithms for the net import spatial price equilibrium problem. J. Cost Analysis , in press.
36.
Nagurney, A.1988c. An algorithm for the solution of a quadratic programming problem with application to constrained matrix and spatial price equilibrium problems. Environment & Planning A, in press.
37.
Nagurney, A., and Aronson, J.1988. A general dynamic spatial price equilibrium model: formulation, solution, and computational results. J. Comput. Appl. Math.22:359-377.
38.
Pang, J.S.1981. A hybrid method for the solution of some multicommodity spatial equilibrium problems. Management Science27:1142-1157.
39.
Pang, J.S.1984. Solution of the general multicommodity spatial equilibrium problem by variational and complementarity methods. J. RegionalScience24:403-414.
40.
Pang, J.S.1985. Asymmetric variational inequality problems over product sets: applications and iterative methods. Math. Programming31:206-219.
41.
Pardalos, P.M., and Rodgers, G.P.1988. Parallel branch and bound algorithms for unconstrained quadratic zero-one programming. In Publications in operations research series, proceedings of the conference on impact of recent computer advances on operations research, in press.
42.
Polito, J., McCarl, B.A., and Morin, T.L.1980. Solution of spatial equilibrium problems with Bender's decomposition. Management Science26:593-605.
43.
Samuelson, P.A.1952. A spatial price equilibrium and linear programming. American Economic Review42:283-303.
44.
Samuelson, P.A.1957. Intertemporal price equilibrium: a prologue to the theory of speculation. Weltwirtschaftliches Archiv79:181-219.
45.
Smith, M.1979. An algorithm for solving asymmetric equilibrium problems with a continuous cost-flow function. Transportation Research17B:365-371.
46.
Stone, J.C.1988. Formulation and solution of economic equilibrium problems. Systems Optimization Laboratory Technical Report 88-7. Stanford University, Department of Operations Research .
47.
Takayama, T., and Judge, G.G.1971. Spatial and temporal price and allocation models. Amsterdam: North-Holland.
48.
Takayama, T., and Uri, N.P.1983. A note on spatial and temporal price and allocation modeling . Regional Science and Urban Economics13:455-470.
49.
Theise, E., and Jones, P.C.1988. Alternative implementations of a diagonalization algorithm for multicommodity spatial price equilibria. Technical Report 88-06. Northwestern University, Department of Industrial Engineering and Management Sciences.
50.
Zhao, L.1989. Variational inequalities in general equilibrium: analysis and computation. Ph.D. dissertation. Brown University, Division of AppliedMathematics.
