Ein allgemeines Dekompositionsverfahren fuer lineare Optimierungsprobleme

Heinemann, Hergen H. (1971): Ein allgemeines Dekompositionsverfahren fuer lineare Optimierungsprobleme. Published in: Zeitschrift fuer betriebswirtschaftliche Forschung No. 22 (1970): pp. 302-317.

Abstract

A Really GENERAL Decomposition Algorithm for Very Large Linear Optimization Problems

Proven theory as Regards Optimality and Finality

Advantageous for very large problems with a rather small percentage of real variables in the optimal solution - Simplex method is used as a calculating sub-routine -

NO SPECIAL STRUCTURE OF MATRIX REQUIRED - Method applicable without change for non-structures as well as for any and all structures of matrix.

Maximum necessary problem size to be calculated with simplex method procedure: a bit more than a matrix of optimal-solution original variables and optimal solution restrictions - single-stage or double-stage decomposition possible - parametric-programming-similar re-calculations possible. For consultancy on slight extensions in theory as well as on important extensions in calculation tactics you may contact Dr. Hergen Heinemann: Hergen.Heinemann"et"alumni.insead.edu

Detailed ABSTRACT of Theory

(1) From the total problem matrix (TPM) partial problems (PP) are taken arbitrarily, but every variable should be represented in at least one of them.

(2) PPA´s are equipped with suitable functions for optimization and are optimized with the simplex method procedure.

(3) The optimized solutions of the PPA´s serve to obtain variables for an auxiliary problem (AP), which is then optimized to reflect an optimal combination of the optimized PP`s.

(4) With the optimal dual values of the AP the actual values for every variable of the to-be-optimized function of the TPM are calculated.

(5) With the actual values for every variable of the to-be-optimized function of the TPM a test is done to check whether the optimal solution of the TPM is already reached.

(6) Is the optimum solution of the TPM reached, then the algorithm is at the end. If not, the algorithm continues with item (2) above with a new set of variables and using the actual values of the variables of the to-be-optimized function as per item (3), starting a new cycle of the algorithm.

Original copy may be available at:

Titel: Ein allgemeines Dekompositionsverfahren fuer lineare Optimierungsprobleme (in English: A General Decomposition Algorithm for Linear Optimization Problems) ( To obtain a copy of this operations research on linear programming paper e-mail to Technische Universitaet, Braunschweig:) [e-mail]

Author: Heinemann, Hergen Published: 1971 No. of pages: III, 80 S. ; 8º Doctoral Degree Paper: Saarbruecken, University, Diss., 1971 Signature: 2400-3106 / Tiefmagazin, 2. UG

• Item Type: MPRA Paper
• English Title: A General Decomposition Algorithm for Linear Optimization Problems
• Language: German
• Keywords: general decomposition algorithm; allgemeiner Dekompositionsalgorithmus; linear optimization problems; lineare Optimierungsprobleme; Dekomposition; linear programming; lineare Programmierung; Operations Research; very large linear optimizationproblems; Dekompositionsalgorithmus fuer lineare Optimierungsprobleme; Dr. Hergen Heinemann; Endlichkeitsbeweis; optimality; finality; Optimalitätsbeweis
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C65 - Miscellaneous Mathematical Tools; C - Mathematical and Quantitative Methods > C0 - General > C02 - Mathematical Methods; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis

References

Abadie, J.M. : Le principe de decomposition de Dantzig et Wolfe, in: Revue Francaise de Recherche Operationelle, 4 (1960), S. 93-115

Abadie, J.M. : On Decomposition Principle, in : Bericht Nr. 63-20 des Operation Research Center der Universität Californien, Berkeley, 1963

Abadie, J.M., A.C. Williams : Dual and parametric methods in decomposition, in : Recent advances in mathematical programming, Hrsg. : Graves, R. u. P. Wolfe, McGraw Hill (1963), S. 149-158

Adam, D. u. W. Roehrs : Ein Algorithmus zur Dekomposition linearer Planungsprobleme, in : Zeitschrift fuer Betriebwirtschaft, 37 (1967), S. 395-417

Adam, D. : Entscheidungsorientierte Kostenbewertung, Wiesbaden 1970, S. 196-230

Balas, E. : An infeasibility pricing decomposition method for linear programs, in : Operations Research (ORSA), 14 (1966), S. 847-873

Balas, E. : Une methode de decomposition quasi-primale-duale pour des programmes lineaires, I-Variable, in : Comptes Rendues de l`Academie des Sciences, Paris, 261 (1965) 4. Oktober, S. 2572-2574

Balas, E. : idem, II-Variante, in : Comptes Rendues de l`Academie des Sciences, Paris, 261 (1965) 18. Oktober, S. 2809-2811

Baumel, W.J., u. T. Fabian : Decomposition, pricing for decentralisation and external economies, in : Management Science, 11 (1964), S. 1-32

Beale, E.M.L., P.A.B. Hughes u. R.E. Small : Experiences in using a decomposition program, in : The Computer, 8 (1965), S. 13-18

Bell, E.J. : Primal-dual decompositon programming, in : Bericht Nr. 65-23 des Operation Research Center der Universität Californien, Berkeley, August 1965

Benders, J.F. : Partition in mathematical programming, Dissertation, Utrecht (1960)

Benders, J.F. : Partitioning procedures for solving mixed-variables programming problems, in : Numerische Mathematik, 4 (1962), S. 238-252

Bennet, J.M. : An approach to some structured linear programming problems, in : Operations Research (ORSA), 14 (1966), S. 636-645

Bennet, J.M. u., D.R. Greene : idem, in : Operations Research (ORSA), 17 (1969), S. 749-750

Dantzig, G.B. : Lineare Programmierung und Erweiterungen, Springer-Verlag, Berlin, Heidelberg, New York 1966

Dantzig, G.B., u. M.B. Shapiro : Solving the chemical equilibrium problem using the decomposition principle, in : Rand-Report P-2056, 10.August 1960

Dantzig, G.B., u. P. Wolfe : A decomposition principle for linear programs, in : Rand-Report P-1544, 10. November 1958, revidiert : 6. November 1959

Dantzig, G.B., u. P. Wolfe : A decomposition principle for linear programs, in :Oprations Research (ORSA) 8 (1960), S. 101-111

Dantzig, G.B., u. P. Wolfe : The decomposition algorithm for linear programs, in : Econometrica, 29 (1961), S. 767-778

Grosse, L. : Loesung groesserer linearer Optimierungsaufgaben mit dem Dekompositionsverfahren nach Dantzig-Wolfe, in : Wissenschaftliche Zeitschrift der Hochschule fuer Oekonomie Berlin, 11 (1966), Heft 2, S. 159-161

Grosse, L. : Loesung groesserer linearer Optimierungsaufgaben mit dem Dekompositionsverfahren nach Dantzig-Wolfe, in : H. Bader u.a. (Hrsg.) : Mathematik und Wirtschaft, Band 4, Westdeutscher Verlag Koeln, Opladen, 1967

Harvey, R.P. : The decomposition principle for linear programming, in : International Journal of Computer Mathematics, 1 (1964), S. 20-35

Heestermann, A.R.G. : Special simplex algorithm for multi-sector problems, in : Numerische Mathematik, 12 (1968), S. 288-306

Heestermann, A.R.R., u. J. Sandee : Special simplex algorithm for linked problems, in : Management Science, 11 (1965), S. 420-427

Heinemann, H. : Ein allgemeines Dekompositionsverfahren für lineare Optimierungsprobleme, in : Zeitschrift fuer betriebswirtschaftliche Forschung, 22 (1970), s. 302-317

Hu, T.G. : A decomposition algorithm for shortest paths in a network, in : IBM Research Report RC-1562, Februar 1966

Hu, T.G. : A decomposition algorithm for shortest paths in a network, in : Operations Research (ORSA), 16 (1968), 91-102

Koenig, J.W.J. : Dynamische Optimierungsmodelle der chemischen Industrie, Dissertation, Hamburg 1968

Kuenzi, H.P., u. S.T. Tan : Lineare Optimierung grosser Systeme, in : Lecture Notes in Mathematics, 27 (1966), Hrsg. : Dold, A., u. B. Eckmann, Springer-Verlag, Berlin, Heidelberg, New York, 1966

Luettken, H. : Reduktion und Dekomposition von PERT-Netzen, in : Ablauf- und Planungsforschung, 8 (1967), S. 370-379

Luettken, H. : Reduktion und Dekomposition von Planungsnetzen, in : Ablauf- und Planungsforschung, 7 (1966), S. 92-104

Macguire, C.B. : Some extension of the Dantzig-Wolfe decomposition scheme, Center for Research in Management Science, Universitaet Californien, Berkeley, Working Paper Nr. 66, Maerz 1963

Marschak, J. : Computation, decomposition and internal pricing, Center for Research in Management Science, Universitaet Californien, Berkeley, Working Paper Nr. 56, Dezember 1962

Mills, G. : A decomposition algorithm for the shortest route problem, in: Oprations Research (ORSA), 14 (1966), S. 279-291

Mueller-Merbach, H. : Das Prinzip der "direkten Dekomposition" in der linearen Planungsrechnung, in : Zeitschrift fuer angewandte Mathematik und Mechanik, 46 (1966), Sonderheft, S. T102-T104

Mueller-Merbach, H. : Das Verfahren der direkten Dekomposition in der linearen Planungsrechnung, in : Ablauf- und Planungsforschung, 6 (1965), S. 306-322

Ohse, D. : Numerische Erfahrungen mit zwei Dekompositionsverfahren der linearen Planungsrechnung, in : Ablauf- und Planungsforschung, 8 (1967), Heft 2, S. 289-301

Nemhauser, G.L. : Decomposition for linear programming by dynamic programming, in : Naval Research Logistics Quarterly, 11 (1964), S. 191-195

Parikh, S.C., u. W.S. Jewell : Decomposition of project network, in : Management Science, 11 (1965), S. 444-459

Rech, P. : Decomposition and interconnected systems in mathematical programming, Bericht Nr. 65-31 des Operations Research Center (ORSA), Universitaet Californien, Berkeley, September 1965

Rosen, J.B. : Convex partition programming, in : Recent advances in mathematical programming, Hrsg.: Graves, R., u. P. Wolfe, McGraw Hill 1963, S. 159-176

Rosen, J.B. : Primal partition programming for block-diagonal matrices, in : Numerische Mathematik,, 6 (1964), S. 250-260

Rosen, J.B., u. J.C. Ornea : Solution of nonlinear programming problems by partitioning, in : Management Science, 10 (1963/1964), S. 160-173

Sanders, J.L. : A nonlinear decomposition principle, in : Operations Research (ORSA), 13 (1965), S. 266-271

Tan, S.T. : Beitraege zur Dekomposition von linearen Programmen (I und II), in : Unternehmensforschung, 10(1966),S. 168-189 und 247-268

Tournol du Clos, J. : Note sur la decomposition matricielle triangulaire. Application a l`inversion matricielle et la resulution des systemes lineaires, in : Revue Francaise d`informatique et des recherche operationelle, Nr. 3, Mai-Juni 1976

Tuy, P.H. : Sur le probleme des constraintes supplementaires en programmation lineaire et son application au probleme de decomposition, in : Elektronische Informationsverarbeitung und Kybernetik, 3 (1967), S. 141.156

Whinston, A. : A decomposition algorithm for quadratic programming, Cowles Foundation, Discussion Paper 172, Yale University, Juni 1964

Whinston, A. : A dual decomposition algorithm for quadratic programming, in : Cahiers du Centre d`Edudes de Recherche Operationelle, 6 (1964), S. 188-201

Zangwill, W.I. : A decomposable nonlinear programming approach, in : Operations Research (ORSA), 15 (1967), S. 1068-1087