Abstract
Most large-scale optimization problems exhibit structures that allow the possibility of attack via algorithms that exhibit a high level of parallelism. The emphasis of this paper is the development of parallel optimization algorithms for a class of convex, block-structured problems. Computational experience is cited for some large-scale problems arising from traffic assignment applications. The algorithms considered here have the property that they allow such problems to be decomposed into a set of smaller optimization problems at each major iteration. These smaller problems correspond to linear single-commodity networks in the traffic assignment case, and they may be solved in parallel. Results are given for the distributed solution of such problems on the CRYSTAL multicomputer.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.P. Bertsekas and E.M. Gafni, “Projection methods for variational inequalities with application to the traffic assignment problem,”Mathematical Programming Study 17 (1982) 139–159.
D.G. Cantor and M. Gerla, “Optimal routing in packet switched computer networks,”IEEE Transactions on Computing 23 (1974) 1062–1068.
R.J. Chen, “Parallel algorithms for a class of convex optimization problems,” Ph.D. Thesis, Computer Sciences Department, University of Wisconsin-Madison, 1987.
R.J. Chen and R.R. Meyer, “A scaled trust region method for a class of convex optimization problems,” University of Wisconsin-Madison Computer Sciences Department Tech. Rpt. #675.
G.B. Dantzig and P. Wolfe, “Decomposition principle for linear programs,”Operations Research 8 (1960) 101–111.
D. DeWitt, R. Finkel and M. Solomon, The CRYSTAL Multicomputer: Design and implementation experiment,”IEEE Transactions on Software Engineering 13 (1987) 953–966.
B. Feijoo, “Piecewise-linear approximation methods and parallel algorithms in optimization,” University of Wisconsin-Madison Computer Sciences Department Tech. Rpt. #598 (1985).
L.J. LeBlanc, E.K. Morlok and W.P. Pierskalla, “An efficient approach to solving the road network equilibrium traffic assignment problem,”Transportation Research 9 (1975) 309–318.
S. Nguyen and C. Dupuis, “An efficient method for computing traffic equilibria in networks with asymmetric transportation,”Transportation Science 18 (1984) 185–202.
P.A. Steenbrink,Optimization of Transport Network (1984) (Wiley, London, New York, 1974).
J.G. Wardrop, “Some theoretical aspects of road traffic research,”Proceedings of the Institute of Civil Engineering, Part II, 1 (1952) 325–378.
J. Zhang, N.H. Kim and L. Lasdon, “An improved successive linear programming algorithm,” University of Texas Graduate School of Business Working Paper 84/85-3-2, Austin (1984).
Author information
Authors and Affiliations
Additional information
This research was supported in part by NSF grant CCR-8709952 and AFOSR grant AFOSR-86-0194.
Rights and permissions
About this article
Cite this article
Chen, R.J., Meyer, R.R. Parallel optimization for traffic assignment. Mathematical Programming 42, 327–345 (1988). https://doi.org/10.1007/BF01589409
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01589409