Skip to main content
SpringerLink
Log in

An advanced implementation of the Dantzig—Wolfe decomposition algorithm for linear programming

  • Published:
Mathematical Programming Submit manuscript

Abstract

Since the original work of Dantzig and Wolfe in 1960, the idea of decomposition has persisted as an attractive approach to large-scale linear programming. However, empirical experience reported in the literature over the years has not been encouraging enough to stimulate practical application. Recent experiments indicate that much improvement is possible through advanced implementations and careful selection of computational strategies. This paper describes such an effort based on state-of-the-art, modular linear programming software (IBM's MPSX/370).

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. I. Alder and A. Ülkücü, “On the number of iterations in Dantzig—Wolfe decomposition”, in: D.M. Himmelblau, ed.,Decomposition of large scale problems (North-Holland, Amsterdam, 1973) pp. 181–187.

    Google Scholar 

  2. E. Beale, P. Huges and R. Small, “Experiences in using a decomposition program”,Computer Journal 8(1965) 13–18.

    Google Scholar 

  3. M. Benichou et al., “The efficient solution of large-scale linear programming problems-some algorithmic techniques and computational results”,Mathematical Programming 13 (1977) 280–332.

    Google Scholar 

  4. P. Broise, P. Huard and J. Sentenac,Decomposition des programmes mathématiques (Dunod, Paris, 1968).

    Google Scholar 

  5. CDC, “APEX-III Reference Manual”, Publication no. 76070000 (1974).

  6. B. Culot, E. Loute and J.K. Ho, “DECOMPSX user's manual”, CORE computing report 80-B-01, C.O.R.E., Université Catholique de Louvain, Belgium, 1980. [In French.]

    Google Scholar 

  7. B. Culot and E. Loute, “DECOMPSX system manual”, CORE computing report 80-B-02, C.O.R.E., Université Catholique de Louvain, Belgium, 1980. [In French.].

    Google Scholar 

  8. B. Culot and E. Loute, “DECOMPSX source”, CORE computing report 80-B-03, C.O.R.E., Université Catholique de Louvain, Belgium, 1980.

    Google Scholar 

  9. G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, 1963).

    Google Scholar 

  10. G.B. Dantzig and P. Wolfe, “The decomposition principle for linear programs”,Operations Research 8 (1960) 101–111.

    Google Scholar 

  11. G.B. Dantzig and P. Wolfe, “The decomposition algorithm for linear programs”,Econometrica 29 (1961) 767–778.

    Google Scholar 

  12. G.B. Dantzig, “On the need for a system optimization laboratory”, in: R. Cottle and J. Krarup, eds.,Optimization methods for resource allocation (Crane—Russack, New York, 1974) pp. 3–24.

    Google Scholar 

  13. Y.M.I. Dirickx and L.P. Jennergren,Systems analysis by multilevel methods (Wiley, New York, 1979).

    Google Scholar 

  14. J. Forrest and J. Tomlin, “Updating triangular factors of the basis in the product form simplex method”,Mathematical Programming 2 (1972) 263–278.

    Google Scholar 

  15. R. Geottle, E. Cherniavsky and R. Tessmer, “An integrated multi-regional energy and interindustry model of the United states”, BNL 22728, Brookhaven National Laboratory, New York, May 1977.

    Google Scholar 

  16. F.G. Gustavson, “Some basic techniques for solving sparse systems of linear equations”, in: D.J. Rose and R.A. Willoughby, eds.,Sparse matrices and their applications (Plenum, New York, 1972) pp. 41–52.

    Google Scholar 

  17. P. Harris, “Pivot selection rules of the Devex LP code”,Mathematical Programming Study 4 (1975) 30–57.

    Google Scholar 

  18. E. Hellerman and D. Rarick, “The partitioned preassigned pivot procedure (P4)” in: D.J. Rose and R.A. Willoughby, eds.,Sparse matrices and their applications (Plenum, New York, 1972) pp. 67–76.

    Google Scholar 

  19. J.K. Ho, “Implementation and application of a nested decomposition algorithm”, in: W.W. White, ed.,Computers and mathematical programming (National Bureau of Standards, 1978) pp. 21–30.

  20. J.K. Ho, E. Loute, Y. Smeers and E. van de Voort, “The use of decomposition techniques for large scale linear programming energy models”, in: A. Strub, ed.,Energy Policy, special issue on “Energy Models for the European Community”, (1979) 94–101.

  21. J.K. Ho and E. Loute, “A comparative study of two methods for staircase linear programs”,ACM Transactions on Mathematical Software 6 (1980) 17–30.

    Google Scholar 

  22. IBM, “Mathematical Programming System Extended (MPSX) Read Communication Format (READCOMM) Program description manual”, SH20-0960-0 (January 1971).

  23. IBM, “IBM Mathematical Programming System Extended/370 (MPSX/370) Program reference manual”, SH19-1095-3 (December 1979).

  24. IBM, “IBM Mathematical Programming System. Extended/370 (MPSX/370) Logic manual”, (licensed material) LY19-1024-0 (January 1975).

  25. J.E. Kalan, “Aspects of large-scale in core linear programming”, in:Proceedings of A.C.M. annual conference (1971) 304–313.

  26. G.P. Kutcher, “On the decomposition price endogenous models”, in: L.M. Goreux and A.S. Manne, eds.,Multi-level planning: Case studies in Mexico (North-Holland, Amsterdam, 1973) pp. 499–519.

    Google Scholar 

  27. L.S. Lasdon,Optimization theory for large systems (McMillan, London, 1970).

    Google Scholar 

  28. H.M. Markowitz, “The elimination form of the inverse and its application to linear programming”,Management Science 3 (1957) 255–269.

    Google Scholar 

  29. W. Orchard—Hays,Advanced linear-programming computing techniques (McGraw—Hill, New York, 1968).

    Google Scholar 

  30. M. Simmonard,Programmation linéaire, Vols. 1 et 2 (Dunod, Paris, 1972).

    Google Scholar 

  31. L. Slate and K. Spielberg, “The extended control language of MPSX/370 and possible applications”,IBM Systems Journal 17 (1978) 64–81.

    Google Scholar 

  32. G. von Schiefer, “Lösung grosser linear Regionalplannungsprobleme mit der Methode von Dantzig und Wolfe”,Zeitschrift für Operations Research, 20 (1976) B1-B16.

    Google Scholar 

  33. H.P. Williams and A.C. Redwood, “A structured programming model in the food industry”,Operational Research Quarterly 25 (1974) 517–527.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Applied Mathematics Department, Brookhaven National Laboratory, 11973, Upton, New York, USA

    James K. Ho

  2. C.O.R.E., Université Catholique de Louvain, 1348, Louvain-la-Neuve, Belgium

    Etienne Loute

Authors
  1. James K. Ho
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Etienne Loute
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The submitted manuscript has been authored under contract DE-AC02-76CH0016 with the U.S. Department of Energy. Accordingly, the U.S. Government retains a nonexclusive royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes.

Research supported by the Belgian National Research program in Energy, contract E/I/3.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ho, J.K., Loute, E. An advanced implementation of the Dantzig—Wolfe decomposition algorithm for linear programming. Mathematical Programming 20, 303–326 (1981). https://doi.org/10.1007/BF01589355

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation