IDEAS home Printed from https://ideas.repec.org/p/pra/mprapa/28842.html
   My bibliography  Save this paper

Ein allgemeines Dekompositionsverfahren fuer lineare Optimierungsprobleme
[A General Decomposition Algorithm for Linear Optimization Problems]

Author

Listed:
  • Heinemann, Hergen H.

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:) fernleihe@tu-bs.de 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

Suggested Citation

  • Heinemann, Hergen H., 1971. "Ein allgemeines Dekompositionsverfahren fuer lineare Optimierungsprobleme [A General Decomposition Algorithm for Linear Optimization Problems]," MPRA Paper 28842, University Library of Munich, Germany.
    • Handle: RePEc:pra:mprapa:28842
    as

    Download full text from publisher

    File URL: https://mpra.ub.uni-muenchen.de/28842/3/MPRA_paper_28842.pdf
    File Function: original version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Egon Balas, 1966. "An Infeasibility-Pricing Decomposition Method for Linear Programs," Operations Research, INFORMS, vol. 14(5), pages 847-873, October.
    2. A. R. G. Heesterman & J. Sandee, 1965. "Special Simplex Algorithm for Linked Problems," Management Science, INFORMS, vol. 11(3), pages 420-428, January.
    3. G. Mills, 1966. "A Decomposition Algorithm for the Shortest-Route Problem," Operations Research, INFORMS, vol. 14(2), pages 279-291, April.
    4. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    5. J. B. Rosen & J. C. Ornea, 1963. "Solution of Nonlinear Programming Problems by Partitioning," Management Science, INFORMS, vol. 10(1), pages 160-173, October.
    6. Willard I. Zangwill, 1967. "A Decomposable Nonlinear Programming Approach," Operations Research, INFORMS, vol. 15(6), pages 1068-1087, December.
    7. T. C. Hu, 1968. "A Decomposition Algorithm for Shortest Paths in a Network," Operations Research, INFORMS, vol. 16(1), pages 91-102, February.
    8. Andrew B. Whinston, 1964. "A Decomposition Algorithm for Quadratic Programming," Cowles Foundation Discussion Papers 172, Cowles Foundation for Research in Economics, Yale University.
    9. J. L. Sanders, 1965. "A Nonlinear Decomposition Principle," Operations Research, INFORMS, vol. 13(2), pages 266-271, April.
    10. Shailendra C. Parikh & William S. Jewell, 1965. "Decomposition of Project Networks," Management Science, INFORMS, vol. 11(3), pages 444-459, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. I-Lin Wang & Ellis L. Johnson & Joel S. Sokol, 2005. "A Multiple Pairs Shortest Path Algorithm," Transportation Science, INFORMS, vol. 39(4), pages 465-476, November.
    2. A. Ruszczynski, 1993. "Regularized Decomposition of Stochastic Programs: Algorithmic Techniques and Numerical Results," Working Papers wp93021, International Institute for Applied Systems Analysis.
    3. Ethem Çanakoğlu & İbrahim Muter & Tevfik Aytekin, 2021. "Integrating Individual and Aggregate Diversity in Top- N Recommendation," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 300-318, January.
    4. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    5. Sankaran, Jayaram K., 1995. "Column generation applied to linear programs in course registration," European Journal of Operational Research, Elsevier, vol. 87(2), pages 328-342, December.
    6. Metrane, Abdelmoutalib & Soumis, François & Elhallaoui, Issmail, 2010. "Column generation decomposition with the degenerate constraints in the subproblem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 37-44, November.
    7. Belanger, Nicolas & Desaulniers, Guy & Soumis, Francois & Desrosiers, Jacques, 2006. "Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1754-1766, December.
    8. Williams, R. Lynn & Dillion, Carl R. & McCarl, Bruce A., 1992. "An Economic Investigation of Edwards Aquifer Water Use Tradeoffs," WAEA/ WFEA Conference Archive (1929-1995) 321395, Western Agricultural Economics Association.
    9. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    10. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    11. Melanie Erhard, 2021. "Flexible staffing of physicians with column generation," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 212-252, March.
    12. Thomas W. M. Vossen & Dan Zhang, 2015. "Reductions of Approximate Linear Programs for Network Revenue Management," Operations Research, INFORMS, vol. 63(6), pages 1352-1371, December.
    13. Ternoy, Jacques Emmanuel, 1969. "Cooperation and economic efficiency," ISU General Staff Papers 196901010800004786, Iowa State University, Department of Economics.
    14. Ibrahim Muter & Tevfik Aytekin, 2017. "Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 405-421, August.
    15. Han, Jialin & Zhang, Jiaxiang & Guo, Haoyue & Zhang, Ning, 2024. "Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm," European Journal of Operational Research, Elsevier, vol. 316(3), pages 958-975.
    16. Canca, David & Barrena, Eva, 2018. "The integrated rolling stock circulation and depot location problem in railway rapid transit systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 115-138.
    17. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    18. Mercedes Esteban-Bravo & Jose M. Vidal-Sanz & Gökhan Yildirim, 2014. "Valuing Customer Portfolios with Endogenous Mass and Direct Marketing Interventions Using a Stochastic Dynamic Programming Decomposition," Marketing Science, INFORMS, vol. 33(5), pages 621-640, September.
    19. Grunert, Tore & Sebastian, Hans-Jurgen, 2000. "Planning models for long-haul operations of postal and express shipment companies," European Journal of Operational Research, Elsevier, vol. 122(2), pages 289-309, April.
    20. Rigo, Cezar Antônio & Seman, Laio Oriel & Camponogara, Eduardo & Morsch Filho, Edemar & Bezerra, Eduardo Augusto & Munari, Pedro, 2022. "A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service," European Journal of Operational Research, Elsevier, vol. 303(1), pages 168-183.

    More about this item

    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;
    All these keywords.

    JEL classification:

    • C65 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Miscellaneous Mathematical Tools
    • C02 - Mathematical and Quantitative Methods - - General - - - Mathematical Economics
    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pra:mprapa:28842. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Joachim Winter (email available below). General contact details of provider: https://edirc.repec.org/data/vfmunde.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.