IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v3y1957i3p255-269.html
   My bibliography  Save this article

The Elimination form of the Inverse and its Application to Linear Programming

Author

Listed:
  • Harry M. Markowitz

    (The RAND Corporation)

Abstract

It is common for matrices in industrial applications of linear programming to have a large proportion of zero coefficients. While every item (raw material, intermediate material, end item, equipment item) in, say, a petroleum refinery may be indirectly related to every other, any particular process uses few of these. Thus the matrix describing petroleum technology has a small percentage of non-zeros. If spacial or temporal distinctions are introduced into the model the percentage of non-zeros generally falls further. The present paper discusses a form of inverse which is especially convenient to obtain and use for matrices with a high percentage of zeros. The application of this form of inverse in linear programming is also discussed.

Suggested Citation

  • Harry M. Markowitz, 1957. "The Elimination form of the Inverse and its Application to Linear Programming," Management Science, INFORMS, vol. 3(3), pages 255-269, April.
    • Handle: RePEc:inm:ormnsc:v:3:y:1957:i:3:p:255-269
    DOI: 10.1287/mnsc.3.3.255
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.3.3.255
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.3.3.255?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dobrzyński, Michał & Plata, Jagoda, 2010. "Fill-ins number reducing direct solver designed for FIT-type matrix," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 80(8), pages 1684-1693.
    2. 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.
    3. Van Ha, Pham & Kompas, Tom, 2016. "Solving intertemporal CGE models in parallel using a singly bordered block diagonal ordering technique," Economic Modelling, Elsevier, vol. 52(PA), pages 3-12.
    4. Defeng Liu & Andrea Lodi & Mathieu Tanneau, 2021. "Learning chordal extensions," Journal of Global Optimization, Springer, vol. 81(1), pages 3-22, September.
    5. Keeping, B.R. & Pantelides, C.C., 1998. "A distributed memory parallel algorithm for the efficient computation of sensitivities of differential-algebraic systems," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 44(6), pages 545-558.
    6. Harry M. Markowitz, 2002. "Efficient Portfolios, Sparse Matrices, and Entities: A Retrospective," Operations Research, INFORMS, vol. 50(1), pages 154-160, February.
    7. Péter Tar & Bálint Stágel & István Maros, 2017. "Parallel search paths for the simplex algorithm," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(4), pages 967-984, December.
    8. Gass, Saul I., 1997. "The Washington operations research connection: the rest of the story," Socio-Economic Planning Sciences, Elsevier, vol. 31(4), pages 245-255, December.
    9. Chung-Han Hsieh, 2022. "On Solving Robust Log-Optimal Portfolio: A Supporting Hyperplane Approximation Approach," Papers 2202.03858, arXiv.org.
    10. Harry M. Markowitz, 2004. "Trains of Thought," Chapters, in: Michael Szenberg & Lall Ramrattan (ed.), Reflections of Eminent Economists, chapter 17, Edward Elgar Publishing.
    11. Porfirio Suñagua & Aurelio R. L. Oliveira, 2017. "A new approach for finding a basis for the splitting preconditioner for linear systems from interior point methods," Computational Optimization and Applications, Springer, vol. 67(1), pages 111-127, May.
    12. Suresh P. Sethi & Sushil Gupta & Vipin K. Agrawal & Vijay K. Agrawal, 2022. "Nobel laureates’ contributions to and impacts on operations management," Production and Operations Management, Production and Operations Management Society, vol. 31(12), pages 4283-4303, December.
    13. LOUTE, Etienne, 2003. "Gaussian elimination as a computational paradigm," LIDAM Discussion Papers CORE 2003059, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Miles Lubin & J. Hall & Cosmin Petra & Mihai Anitescu, 2013. "Parallel distributed-memory simplex for large-scale stochastic LP problems," Computational Optimization and Applications, Springer, vol. 55(3), pages 571-596, July.
    15. Tobias Achterberg & Robert E. Bixby & Zonghao Gu & Edward Rothberg & Dieter Weninger, 2020. "Presolve Reductions in Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 473-506, April.
    16. Milan Dražić & Rade Lazović & Vera Kovačević-Vujčić, 2015. "Sparsity preserving preconditioners for linear systems in interior-point methods," Computational Optimization and Applications, Springer, vol. 61(3), pages 557-570, July.

    More about this item

    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:inm:ormnsc:v:3:y:1957:i:3:p:255-269. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.