A data-level parallel linear-quadratic penalty algorithm for multicommodity network flows

ABSTRACT

We describe the development of a data-level, massively parallel, software system for the solution of multicommodity network flow problems. Using a smooth linear-quadratic penalty (LQP) algorithm we transform the multicommodity network flow problem into a sequence of independent min-cost network flow subproblems. The solution of these problems is coordinated via a simple, dense, nonlinear master program to obtain a solution that is feasible within some user-specified tolerance to the original multicommodity network flow problem. Particular emphasis is placed on the mapping of both the subproblems and master problem data to the processing elements of a massively parallel computer, the Connection Machine CM-2. As a result of this design we can solve large and sparse optimization problems on current SIMD massively parallel architectures. Details of the implementation are reported, together with summary computational results with a set of test problems drawn from a Military Airlift Command application.

REFERENCES

• 1: ASSAD, A. A. 1978. Multicommodity network fiows--a survey. Networks 8, 37-91.
• 2: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 3: BERTSEKAS, D. P., CASTANON, D., ECKSTEIN, J., AND ZENIOS, S. A. 1994. Parallel computing in network optimization. In Handbooks in Operations Research. North-Holland, Amsterdam. To be published.
• 4: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• 5: Jeffery L. Kennington , Sandra Niemi , Stephen J. Wichmann, An empirical evaluation of the KORBX algorithms for military airlift applications, Operations Research, v.38 n.2, p.240-248, Mar–Apr. 1990 [doi>10.1287/opre.38.2.240]
• 6: CENSOR, Y. AND LENT, A. 1981. An lterative row-action method for interval convex programming. J. Opt~m. Theory Appl. 34, 321-353.
• 7: Y. Censor , S. A. Zenios, Proximal minimization algorithm with D-functions, Journal of Optimization Theory and Applications, v.73 n.3, p.451-464, June 1992 [doi>10.1007/BF00940051]
• 8: HEARN, D. W., LAWPHONGPANICH, S., AND VENTURA, J. A. 1987. Restricted simplicial decomposition: Computation and extensions. Math Program Study 31, 99-118
• 9: HmLIS, W. D. 1985. The Connection Machine. The MIT Press, Cambridge, Mass.
• 10: JOHNSSON, S. L. AND HO, C. T. 1987. Algorithms for multiplying matrices of arbitrary shapes using shared memory primitives on boolean cubes. YALEU/DCS/TR-569, Dept. of Computer Science, Yale Univ., New Haven, Conn.
• 11: KENNINGTON, J L. 1978. A survey of linear multmommod~ty network flows. Oper. Res. 26, 209-236.
• 12: Jeff L. Kennington , Richard V. Helgason, Algorithms for Network Programming, John Wiley & Sons, Inc., New York, NY, 1980
• 13: MULVEY, J. M., ZENIOS, S. A., AND AHLFELD, D. P. 1990. Simplicial decompositmn for convex generalized networks. J Inf. Optim Scl. 11,359-387.
• 14: Soren S. Nielsen , Stavros A. Zenios, Proximal minimizations with D-functions and the massively parallel solution of linear network programs, Computational Optimization and Applications, v.1 n.4, p.375-398, April 1993
• 15: NIELSEN, S. N. AND ZENIOS, S. A. 1992. Massively parallel algorithms for singly constrained nonlinear programs ORSA J. Comput. 4, 166-181.
• 16: P~NAR, M ~. AND ZENIOS, S. A. 1994. On smoothing exact penalty functions for convex constrained optimization. SIAM J. Optim. 4, 3, 486-511.
• 17: PINAR, M. ~. AND ZENIOS, S. A. 1992. Parallel decomposition of multicommodity network flows using linear-quadratic penalty functions. ORSA J. Comput. 4, 235-249.
• 18: ROCKAFELLAR, T. R. 1976a. Augmented Lagrangians and apphcations to proximal point algorithms m convex programming. Math. cper. Res. 1, 97-116.
• 19: ROCKAFELLAR, T. R. 1976b Monotone operators and the proxnnal point algorithm. SIAM J. Control Optim. 14,877-898
• 20: SCHULTZ, G. L. AND MEYER, R. R. 1991. An interior point method for block angular optimizatmn. SIAM J. Opt~m. 1,583-602.
• 21: VON HOHENBALKEN, B. 1977. Slmplicial decompositmn in nonlinear programming algorithms. Math. Program. 13, 49 68.
• 22: ZENIOS, A. S. 1991. On the fine~gram decomposition of multicommodity transportation problems. SIAM J. Optzm. 1. 643 669
• 23: S. A. Zenios , R. A. Lasken, Nonlinear network optimization on a massively parallel connection machine, Annals of Operations Research, v.14 n.1-4, p.147-165, June 1988 [doi>10.1007/BF02186478]
• 24: ZENIOS, S. A., PINAR, M. ~., AND DEMBO, R. S. 1994. A smooth penalty function algorithm for network structured problems. Eur. J. Oper. Res To be published.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

  E. Data

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization; Nonlinear programming

General Terms:
Algorithms, Performance

Keywords:
massively parallel algorithms, multicommodity network problems, parallel optimization