Skip to main content
SpringerLink
Log in

Parallel solution of large-scale, block-angular linear programs

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Many important large-scale optimization problems can be formulated as linear programs with a block-angular structure. This structure lends itself naturally to parallel solutions and is used to great advantage in the solution method described. To demonstrate the efficiency of the method, it has been implemented and computationally tested on both a shared-memory vector multiprocessor (CRAY-2) and a local-memory hypercube (NCUBE/seven) with 64 processors. Computational results for problems with as many as 24,000 rows and 74,000 columns (1,024 blocks and 1.4 million nonzero elements) are presented. A problem of this size was solved on the NCUBE in less than four minutes and the CRAY-2 in 37 seconds.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. W.J. Carolan et al., An empirical evaluation of the KORBX algorithms for military airlift applications, Technical Report 89-OR-86, CINCMAC Analysis Group, Scott AFB, Illinois (1989).

    Google Scholar 

  2. J.L. Gustavson, G.R. Montry and R.E. Benner, Development of parallel methods for a 1024-processor hypercube, SIAM J. Sci. Stat. Computing 9(1988)609–638.

    Article  Google Scholar 

  3. J. Ho and E. Loute, Computational experience with advanced implementation of decomposition algorithms for linear programming, Math. Progr. 27(1983)283–290.

    Google Scholar 

  4. L.S. Lasdon,Optimization Theory for Large Systems (Macmillan, London, 1970).

    Google Scholar 

  5. R.S. Maier, Parallel solution of large-scale structured optimization problems, Ph.D. Dissertation, University of Minnesota (1989).

  6. D. Medhi, Parallel bundle-based decomposition for large-scale structured mathematical programming problems, Ann. Oper. Res., this volume.

  7. K. Murty,Linear Programming (Wiley, New York, 1983).

    Google Scholar 

  8. J.B. Rosen, Primal partition programming for block diagonal matrices, Numerische Mathematik 6(1964)250–260.

    Article  Google Scholar 

  9. R.J.-B. Wets,Numerical Techniques for Stochastic Optimization (Springer-Verlag, Berlin, 1988).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA

    J. B. Rosen & Robert S. Maier

Authors
  1. J. B. Rosen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert S. Maier
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research supported in part by NSF/CER Grant DCR 8420935, AFOSR 87-0127, and the Minnesota Supercomputer Institute.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rosen, J.B., Maier, R.S. Parallel solution of large-scale, block-angular linear programs. Ann Oper Res 22, 23–41 (1990). https://doi.org/10.1007/BF02023046

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02023046

Keywords

Search

Navigation