Abstract
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 concentrating on the many variants that can be derived from logarithmic barrier methods. Full implementation details of the primal-dual predictor-corrector code OB1 are given, including preprocessing, matrix orderings, and matrix factorization techniques. A computational comparison of OB1 with a state-of-the-art simplex code using eight large models is given. In addition, computational results are presented where OB1 is used to solve two very large models that have never been solved by any simplex code INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
Interior point methodSimplexLinear programmingComputer scienceCode (set theory)PreprocessorSimplex algorithmState (computer science)Matrix (chemical analysis)Field (mathematics)AlgorithmMathematical optimizationMathematicsProgramming languageCombinatoricsPure mathematics
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—Progress in Linear Programming
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...
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...
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...
On Finding Primal- and Dual-Optimal Bases
We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for on...
Publication Info
- Year
- 1994
- Type
- article
- Volume
- 6
- Issue
- 1
- Pages
- 1-14
- Citations
- 308
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
308
OpenAlex
12
Influential
270
CrossRef
Cite This
Irvin J. Lustig,
Roy E. Marsten,
David F. Shanno
(1994).
Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art.
INFORMS Journal on Computing
, 6
(1)
, 1-14.
https://doi.org/10.1287/ijoc.6.1.1
Identifiers
- DOI
- 10.1287/ijoc.6.1.1