Skip to main content
SpringerLink
Log in

Decomposition of linear programs using parallel computation

  • Published:
Mathematical Programming Submit manuscript

Abstract

This paper describes DECOMPAR: an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular linear programs using parallel processing of the subproblems. The software is based on a robust experimental code for LP decomposition and runs on the CRYSTAL multicomputer at the University of Wisconsin-Madison. Initial computational experience is reported. Promising directions in future development of this approach are discussed.

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. G.B. Dantzig and P. Wolfe. “The decomposition principle for linear programs,”Operations Research 8 (1960) 101–111.

    Google Scholar 

  2. D. Dewitt, R. Finkel and M. Solomon, “The CRYSTAL multicomputer: design and implementation experience,” Technical Report 553, Computer Science Department, The University of Wisconsin-Madison, September, 1984.

  3. J.K. Ho and W. McKenney, “Triangularity of the basis in linear programs for material requirements planning,”Operations Research Letters 7(6) (1988) 273–278.

    Google Scholar 

  4. J.K. Ho, “Recent advances in the decomposition approach to linear programming,”Mathematical Programming Study 31 (1987) 119–128.

    Google Scholar 

  5. J.K. Ho and E. Loute, “An advanced implementation of the Dantzig-Wolfe decomposition algorithm for linear programming,”Mathematical Programming 20 (1981) 303–326.

    Google Scholar 

  6. J.K. Ho and E. Loute, “Computational aspects of DYNAMICO: a model of trade and development in the world economy,”Revue Française d'Automatique, Informatique et Recherche Opérationelle 18 (1984) 403–414.

    Google Scholar 

  7. R.P. Sundarraj, “Documentation of DECOMP: A Dantzig-Wolfe decomposition code for linear programming,” Master's Thesis, Management Science Program, The University of Tennessee, Knoxville, 1987.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Management Science Program, College of Business Administration, University of Tennesse, 37996-0562, Knoxville, TN, USA

    James K. Ho, Tak C. Lee & R. P. Sundarraj

Authors
  1. James K. Ho
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tak C. Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. P. Sundarraj
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research supported in part by the Office of Naval Research under grant N00014-87-K-0163.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ho, J.K., Lee, T.C. & Sundarraj, R.P. Decomposition of linear programs using parallel computation. Mathematical Programming 42, 391–405 (1988). https://doi.org/10.1007/BF01589413

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation