Abstract
There is little doubt that barrier methods are now indispensable tools in the solution of large-scale linear programming problems. However, it is our opinion that the results of Lustig, Marsten, and Shanno (hereafter LMS) somewhat overstate the performance of these methods relative to the simplex method. We will present a slightly different view of progress in linear programming, one in which barrier methods do not dominate in the solution of large-scale problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
Linear programmingSimplex algorithmComputer scienceScale (ratio)Mathematical optimizationOperations researchMathematicsAlgorithm
Affiliated Institutions
Related Publications
Commentary—Interior-Point Methods: Algorithms and Formulations
The paper by Lustig, Marsten, and Shanno (LMS) gives an excellent presentation of the current state of the art for interior-point methods (as represented by their OB1 code) as i...
Commentary—Major Cholesky Would Feel Proud
Probably more than any other group, authors Lustig, Marsten, and Shanno have led the way in demonstrating the effectiveness of interior methods for solving large, real-world lin...
Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
A survey of the significant developments in the field of interior point methods for linear programming is presented, beginning with Karmarkar's projective algorithm and concentr...
Commentary—Theory and Practice for Interior-Point Methods
The last decade has been a fascinating time for researchers interested in linear programming and its extensions. It opened with Narendra Karmarkar's theoretical paper on the com...
State-of-the-Art Survey—The Traveling Salesman Problem: A Neural Network Perspective
This paper surveys the “neurally” inspired problem-solving approaches to the traveling salesman problem, namely, the Hopfield-Tank network, the elastic net, and the self-organiz...
Publication Info
- Year
- 1994
- Type
- article
- Volume
- 6
- Issue
- 1
- Pages
- 15-22
- Citations
- 87
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
87
OpenAlex
1
Influential
86
CrossRef
Cite This
Robert E. Bixby
(1994).
Commentary—Progress in Linear Programming.
INFORMS Journal on Computing
, 6
(1)
, 15-22.
https://doi.org/10.1287/ijoc.6.1.15
Identifiers
- DOI
- 10.1287/ijoc.6.1.15