An advanced implementation of the Dantzig-Wolfe decomposition algorithm for linear programming. (English) Zbl 0468.90042


90C06 Large-scale problems in mathematical programming
90C05 Linear programming
65K05 Numerical mathematical programming methods
Full Text: DOI


[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.
[2] E. Beale, P. Huges and R. Small, ”Experiences in using a decomposition program”,Computer Journal 8(1965) 13–18. · Zbl 0138.15602
[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. · Zbl 0384.90084
[4] P. Broise, P. Huard and J. Sentenac,Decomposition des programmes mathématiques (Dunod, Paris, 1968). · Zbl 0155.28301
[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.]
[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.].
[8] B. Culot and E. Loute, ”DECOMPSX source”, CORE computing report 80-B-03, C.O.R.E., Université Catholique de Louvain, Belgium, 1980.
[9] G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, 1963).
[10] G.B. Dantzig and P. Wolfe, ”The decomposition principle for linear programs”,Operations Research 8 (1960) 101–111. · Zbl 0093.32806
[11] G.B. Dantzig and P. Wolfe, ”The decomposition algorithm for linear programs”,Econometrica 29 (1961) 767–778. · Zbl 0104.14305
[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.
[13] Y.M.I. Dirickx and L.P. Jennergren,Systems analysis by multilevel methods (Wiley, New York, 1979). · Zbl 0517.90024
[14] J. Forrest and J. Tomlin, ”Updating triangular factors of the basis in the product form simplex method”,Mathematical Programming 2 (1972) 263–278. · Zbl 0288.90048
[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.
[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.
[17] P. Harris, ”Pivot selection rules of the Devex LP code”,Mathematical Programming Study 4 (1975) 30–57. · Zbl 0395.90046
[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.
[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. · Zbl 0432.90048
[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.
[27] L.S. Lasdon,Optimization theory for large systems (McMillan, London, 1970). · Zbl 0224.90038
[28] H.M. Markowitz, ”The elimination form of the inverse and its application to linear programming”,Management Science 3 (1957) 255–269. · Zbl 0995.90592
[29] W. Orchard–Hays,Advanced linear-programming computing techniques (McGraw–Hill, New York, 1968).
[30] M. Simmonard,Programmation linéaire, Vols. 1 et 2 (Dunod, Paris, 1972).
[31] L. Slate and K. Spielberg, ”The extended control language of MPSX/370 and possible applications”,IBM Systems Journal 17 (1978) 64–81. · Zbl 0378.68017
[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. · Zbl 0324.90088
[33] H.P. Williams and A.C. Redwood, ”A structured programming model in the food industry”,Operational Research Quarterly 25 (1974) 517–527. · Zbl 0292.90055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.