Distributed nested decomposition of staircase linear programs

ABSTRACT

This article considers the application of a primal nested-decomposition method to solve staircase linear programs (SLPs) on distributed-memory, multiple-instruction-multiple-data computers. Due to the coupling that exists among the stages of an SLP, a standard parallel-decompositon algorithm for these problems would allow only a subset of the subproblem processes to overlap with one another at any give time. We propose algorithms that seek to increase the amount of overlap among the processes as well as utilize idle time beneficially. Computational results testing the effectiveness of our algoritms are reported, using a standard set of test problems.

REFERENCES

• 1: BARR, R. S. AND HICKMAN, B. 1993. Reporting computational experiments with parallel algorithms: Issues, measures and experts' opintions. ORSA J. Comput. 5, 1, 2-18.
• 2: Tilmann Bönniger , Rüdiger Esser , Dietrich Krekel, CM-5E, KSR2, Paragon XP/S: a comparative description of massively parallel computers, Parallel Computing, v.21 n.2, p.199-232, Feb. 1995 [doi>10.1016/0167-8191(94)00075-L]
• 3: DANTZIG, a. B. AND WOLFE, P. 1960. The decomposition principle for linear programs. Oper. Res. 8, 101-111.
• 4: Robert Entriken , George B. Dantzig, The parallel decomposition of linear programs, 1989
• 5: J. J. H. Forrest , J. A. Tomlin, Vector processing in simplex and interior methods for linear programming, Annals of Operations Research, v.22 n.1-4, p.71-100, Jan. 1990 [doi>10.1007/BF02023049]
• 6: FOURER, R. 1979. Solving staircase linear programs by simplex method, 1: Inversion. Ph.D dissertation, Stanford Univ., Stanford, Calif.
• 7: GAY, D. 1985. Electronic mail distribution of linear programming test problems. COAL Newslett. 13, 10-12.
• 8: GLASSEY, R.C. 1973. Nested decomposition of multi-stage linear programs. Manage. Sci. 20, 282-292.
• 9: S. Kingsley Gnanendran , James K. Ho, Load balancing in the parallel optimization of block-angular linear programs, Mathematical Programming: Series A and B, v.62 n.1, p.41-67, Oct. 21, 1993 [doi>10.1007/BF01585159]
• 10: Ho, J.K. 1976. Implementation and application of a nested decomposition algorithm. In Proceedings of the Bicentennial Conference on Mathematical Programming (Gaithersburg, Md.), 21-30.
• 11: Ho, J. K. 1980. A successive linear optimization approach to the dynamic traffic assignment problem. Transp. Sci. 14, 295-305.
• 12: Ho, J. K. AND LOUTE, E. 1980. A set of staircase linear programming test problems. Math. Program. 20, 245-250.
• 13: Ho, J. K. AND MANNE, A. S. 1974. Nested decomposition of dynamic models. Math. Program. 6, 121-140.
• 14: Ho, J. K. AND SUNDARRAJ, R.P. 1993. A timing model for the revised simplex method. Oper. Res. Lett. 13, 67-73.
• 15: James K. Ho , R. P. Sundarraj, On the efficacy of distributed simplex algorithms for linear programming, Computational Optimization and Applications, v.3 n.4, p.349-363, Oct. 1994 [doi>10.1007/BF01299209]
• 16: J. K. Ho , T. C. Lee , R. P. Sundarraj, Decomposition of linear programs using parallel computation, Mathematical Programming: Series A and B, v.42 n.2, p.391-405, February 1, 1988 [doi>10.1007/BF01589413]
• 17: Alan H. Karp, Programming for parallelism, Computer, v.20 n.5, p.43-57, May 1987 [doi>10.1109/MC.1987.1663563]
• 18: MAIER, R. 1989. Parallel solution of large-scale structured optimization problems. Ph.D dissertation, Univ. of Minnesota, Minneapolis, Minn.
• 19: Deepankar Medhi, Parallel bundle-based decomposition for large-scale structured mathematical programming problems, Annals of Operations Research, v.22 n.1-4, p.101-127, Jan. 1990 [doi>10.1007/BF02023050]
• 20: MURTAGH, B. AND SAUNDERS, M. 1983. MINOS 5.1 user's guide. Rev. ed. Rep. SOL 83-2OR. Dept. of Operations Research, Stanford Univ., Stanford, Calif.
• 21: NEVES, K. W. 1984. Vectorization of scientific software. In High Speed Computations. NATO ASI Series, vol. 7. Springer-Verlag, Berlin, 277-291.
• 22: ROSEN, J.B. 1964. Primal partitioning programming for block diagonal matrices. Numer. Math. 6, 250-260.
• 23: J. B. Rosen , R. S. Maier, Parallel solution of large-scale, block-angular linear, Annals of Operations Research, v.22 n.1-4, p.23-41, Jan. 1990 [doi>10.1007/BF02023046]
• 24: TOMLIN, J.A. 1973. LPMluser's guide. Systems Optimization Laboratory, Stanford Univ., Stanford, Calif. Unpublished.

INDEX TERMS

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

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Experimentation

Keywords:
computational linear programming, distributed computation