Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2017 | OriginalPaper | Chapter

7. Basis Inverse and Update Methods

Authors : Nikolaos Ploskas, Nikolaos Samaras

Published in: Linear Programming Using MATLAB®

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The computation of the basis inverse is the most time-consuming step in simplex-type algorithms. The basis inverse does not have to be computed from scratch at each iteration, but updating schemes can be applied to accelerate this calculation. This chapter presents two basis inverse and two basis update methods used in simplex-type algorithms: (i) Gauss-Jordan elimination basis inverse method, (ii) LU Decomposition basis inverse method, (iii) Product Form of the Inverse basis update method, and (iv) Modification of the Product Form of the Inverse basis update method. Each technique is presented with: (i) its mathematical formulation, (ii) a thorough numerical example, and (iii) its implementation in MATLAB. Finally, a computational study is performed. The aim of the computational study is to compare the execution time of the basis inverse and update methods and highlight the significance of the choice of the basis update method on simplex-type algorithms and the reduction that it can offer to the solution time.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Pivoting Rules
next chapter Revised Primal Simplex Algorithm
Appendix
Available only for authorised users
Literature
1.
Badr, E. S., Moussa, M., Papparrizos, K., Samaras, N., & Sifaleras, A. (2006). Some computational results on MPI parallel implementations of dense simplex method. In Proceedings of World Academy of Science, Engineering and Technology, 23, (CISE 2006), Cairo, Egypt, 39–32.
2.
Bartels, R. H., & Golub, G. H. (1969). The simplex method of linear programming using LU decomposition. Communications of the ACM, 12, 266–268.CrossRef
3.
Benhamadou, M. (2002). On the simplex algorithm revised form. Advances in Engineering Software, 33(11–12), 769–777.CrossRef
4.
Brayton, R. K., Gustavson, F. G., & Willoughby, R. A. (1970) Some results on sparse matrices. Mathematics of Computation, 24, 937–954.MathSciNetCrossRef
5.
Chvatal, V. (1983). Linear programming. New York, USA: W.H. Freeman and Company.MATH
6.
Dantzig, G. B., & Orchard–Hays, W. (1954). The product form of the inverse in the simplex method. Mathematical Tables and Other Aids to Computation, 8, 64–67.MathSciNetCrossRef
7.
Forrest, J. J. H., & Tomlin, J. A. (1972). Updated triangular factors of the basis to maintain sparsity in the product form simplex method. Mathematical Programming, 2, 263–278.MathSciNetCrossRef
8.
Goldfarb, D. (1977). On the Bartels-Golub decomposition for linear programming bases. Mathematical Programming, 13, 272–279.MathSciNetCrossRef
9.
Golub, G. H., & Van Loan, C. F. (2013). Matrix computations (4th ed). JHU Press.
10.
Lim, S., Kim, G., & Park, S. (2003). A comparative study between various LU update methods in the simplex method. Journal of the Military Operations Research Society of Korea, 29(1), 28–42.
11.
Markowitz, H. (1957). The elimination form of the inverse and its applications to linear programming. Management Science, 3, 255–269.MathSciNetCrossRef
12.
McCoy, P. F., & Tomlin, J. A. (1974). Some experiments on the accuracy of three methods of updating the inverse in the simplex method. Technical Report, Stanford University.
13.
Nazareth, J. L. (1987). Computer solution of linear programs. Oxford, UK: Oxford University Press.MATH
14.
Ploskas, N. (2014). Hybrid optimization algorithms: implementation on GPU. Ph.D. thesis, Department of Applied Informatics, University of Macedonia.
15.
Ploskas, N., & Samaras, N. (2013). Basis update on simplex type algorithms. In Book of Abstracts of the EWG-DSS Thessaloniki 2013, p. 11, Thessaloniki, Greece.
16.
Ploskas, N., & Samaras, N. (2013). A computational comparison of basis updating schemes for the simplex algorithm on a CPU-GPU system. American Journal of Operations Research, 3, 497–505.CrossRef
17.
Ploskas, N., Samaras, N., & Margaritis, K. (2013). A parallel implementation of the revised simplex algorithm using OpenMP: Some Preliminary Results. In A. Migdalas et al. (Eds.), Optimization Theory, Decision Making, and Operations Research Applications, Series Title: Springer Proceedings in Mathematics & Statistics 31 (pp. 163–175). New York: Springer.
18.
Ploskas, N., Samaras, N., & Papathanasiou, J. (2012). LU decomposition in the revised simplex algorithm. In Proceedings of the 23th National Conference, Hellenic Operational Research Society (pp. 77–81), Athens, Greece.
19.
Ploskas, N., Samaras, N., & Papathanasiou, J. (2013). A web-based decision support system using basis update on simplex type algorithms. In J. Hernandez et al. (Eds.), Decision Support Systems II Recent Developments Applied to DSS Network Environments, Lecture Notes in Business Information Processing (LNBIP 164) (pp. 102–114). New York: Springer.CrossRef
20.
Ploskas, N., Samaras, N., & Sifaleras, A. (2009). A parallel implementation of an exterior point algorithm for linear programming problems. In Proceedings of the 9th Balcan Conference on Operational Research (BALCOR 2009), 2–6 September, Constanta, Romania.
21.
Reid, J. (1982). A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases. Mathematical Programming, 24, 55–69.MathSciNetCrossRef
22.
Saunders, M. (1976). A fast and stable implementation of the simplex method using Bartels-Golub updating. In J. Bunch, & S. T. Rachev (Eds.), Sparse Matrix Computation (pp. 213–226). New York: Academic Press.CrossRef
23.
Suhl, L. M., & Suhl, U. H. (1993). A fast LU update for linear programming. Annals of Operations Research, 43(1), 33–47.MathSciNetCrossRef
Metadata
Title
Basis Inverse and Update Methods
Authors
Nikolaos Ploskas
Nikolaos Samaras
Copyright Year
2017
Book
Linear Programming Using MATLAB®

Print ISBN: 978-3-319-65917-6

Electronic ISBN: 978-3-319-65919-0

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-65919-0_7

Premium Partner

    Image Credits