article

Free access

The simplex method of linear programming using LU decomposition

Authors:

Richard H. Bartels,

Gene H. GolubAuthors Info & Claims

Communications of the ACM, Volume 12, Issue 5

Pages 266 - 268

https://doi.org/10.1145/362946.362974

Published: 01 May 1969 Publication History

PDF eReader

Abstract

Standard computer implementations of Dantzig's simplex method for linear programming are based upon forming the inverse of the basic matrix and updating the inverse after every step of the method. These implementations have bad round-off error properties. This paper gives the theoretical background for an implementation which is based upon the LU decomposition, computed with row interchanges, of the basic matrix. The implementation is slow, but has good round-off error behavior. The implementation appears as CACM Algorithm 350.

References

[1]

BARTELS, R. H., AND GOLUB, G.H. Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equations. Comm. ACM 11, 6 (June 1968), 401-406.

Digital Library

Google Scholar

[2]

DANTZIG, G.B. Linear Programming and Extensions. Princeton U. Press, Princeton, N.J., 1963.

Google Scholar

[3]

HADLEY, G. Linear Programming. Addison-Wesley, Reading, Mass., 1962.

Google Scholar

[4]

WILKINSON, J. H. Rounding Errors in Algebraic Processes. Prentice-Hall Series in Automatic Computation, Englewood Cliffs, N.J., 1963.

Digital Library

Google Scholar

[5]

BARTELS, RICHARD H. A numerical investigation of the simplex method. Tech. Rep. No. CS 104, Comput. Sci. Dep., Stanford U., Stanford, Calif., July 1968.

Google Scholar

Cited By

View all

He ZSong LLucas RCong JZhang ZPutnam A(2024)LevelST: Stream-based Accelerator for Sparse Triangular SolverProceedings of the 2024 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3626202.3637568(67-77)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1145/3626202.3637568
Liu JElsayed SEssam DSarker RGaranovich IWeir T(2024)Large-Scale Project Portfolio Selection and Scheduling Problem: A Comparison of Exact Solvers and Metaheuristics2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612051(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612051
Pathiranage INeumann A(2024)Multi-Objective Evolutionary Optimization for Large-Scale Open Pit Mine Scheduling2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612008(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612008
Show More Cited By

Index Terms

The simplex method of linear programming using LU decomposition
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
    2. Numerical analysis
      1. Computations on matrices
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
  2. Randomness, geometry and discrete structures
    1. Error-correcting codes

Recommendations

Algorithm 350: simplex method procedure employing Lu decomposition [H]
A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical ...
Klee-Minty's LP and upper bounds for Dantzig's simplex method

Kitahara and Mizuno (2010) [2] get two upper bounds for the number of different basic feasible solutions generated by Dantzig's simplex method. The size of the bounds highly depends on the ratio between the maximum and the minimum values of all the ...

Comments

Information & Contributors

Information

Published In

Communications of the ACM Volume 12, Issue 5

May 1969

95 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/362946

Editor:
M. Stuart Lynn
IBM Research Center, Houston, TX

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1969

Published in CACM Volume 12, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

207
Total Citations
View Citations
3,614
Total Downloads

Downloads (Last 12 months)399
Downloads (Last 6 weeks)75

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

He ZSong LLucas RCong JZhang ZPutnam A(2024)LevelST: Stream-based Accelerator for Sparse Triangular SolverProceedings of the 2024 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3626202.3637568(67-77)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1145/3626202.3637568
Liu JElsayed SEssam DSarker RGaranovich IWeir T(2024)Large-Scale Project Portfolio Selection and Scheduling Problem: A Comparison of Exact Solvers and Metaheuristics2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612051(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612051
Pathiranage INeumann A(2024)Multi-Objective Evolutionary Optimization for Large-Scale Open Pit Mine Scheduling2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612008(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612008
Kirsal Y(2023)Analytical Approaches to QoS Analysis and Performance Modelling in Fog ComputingMulti-Disciplinary Applications of Fog Computing10.4018/978-1-6684-4466-5.ch007(121-151)Online publication date: 23-Jun-2023
https://doi.org/10.4018/978-1-6684-4466-5.ch007
Sun CFortin JTang GWang S(2023)Prediction of dispersion and attenuation on elastic wave velocities in partially saturated rock based on the fluid distribution obtained from three-dimensional (3D) micro-CT imagesFrontiers in Earth Science10.3389/feart.2023.126752211Online publication date: 24-Aug-2023
https://doi.org/10.3389/feart.2023.1267522
Yampolsky TTalmon RLindenbaum O(2023)Domain and Modality Adaptation Using Multi-Kernel Matching2023 31st European Signal Processing Conference (EUSIPCO)10.23919/EUSIPCO58844.2023.10290039(1285-1289)Online publication date: 4-Sep-2023
https://doi.org/10.23919/EUSIPCO58844.2023.10290039
Gupta MWadhvani RRasool A(2023)A real-time adaptive model for bearing fault classification and remaining useful life estimation using deep neural networkKnowledge-Based Systems10.1016/j.knosys.2022.110070259:COnline publication date: 10-Jan-2023
https://dl.acm.org/doi/10.1016/j.knosys.2022.110070
Cabrero-Holgueras JPastrana S(2023)Towards automated homomorphic encryption parameter selection with fuzzy logic and linear programmingExpert Systems with Applications10.1016/j.eswa.2023.120460229(120460)Online publication date: Nov-2023
https://doi.org/10.1016/j.eswa.2023.120460
Fakih SMabrouk MBatton-Hubert MLacarriere B(2023)Bi-level and multi-objective optimization of renewable energy sources and storage planning to support existing overloaded electricity gridsEnergy Reports10.1016/j.egyr.2023.08.01510(1450-1466)Online publication date: Nov-2023
https://doi.org/10.1016/j.egyr.2023.08.015
PAN PPAN P(2023)Implementation of Simplex MethodLinear Programming Computation10.1007/978-981-19-0147-8_4(95-118)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-981-19-0147-8_4
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Algorithm 350: simplex method procedure employing Lu decomposition [H]

A simplex algorithm for piecewise-linear programming I: Derivation and proof

Klee-Minty's LP and upper bounds for Dantzig's simplex method

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations