Paper Info
Title
Computational results of an interior point algorithm for large scale linear programming
Abstract
This paper gives computational results for an efficient implementation of a variant of dual projective algorithm for linear programming. The implementation uses the preconditioned conjugate gradient method for computing projections. Our computational experience reported in this paper indicates that this algorithm has potential as an alternative for solving very large LPs in which the direct methods fail due to memory and CPU time requirements. The conjugate gradient algorithm was able to find very accurate directions even when the system was ill-conditioned. The paper also discusses a new mathematical technique called the reciprocal estimates for estimating the primal variables. We have conducted extensive computational experiments on problems representative of large classes of applications of current interest. We have also chosen instances of the problems of future potential interest, which could not be solved in the past due to the weakness of the prior solution methods, but which represent a large class of new applications. The hypergraph model is such an example. Comparison of our implementation with MINOS 5.1 shows that our implementation is orders of magnitude faster than MINOS 5.1 for these problems.
Year
DOI
Venue
1991
10.1007/BF01582905
Math. Program.
Keywords
Field
DocType
linear program,direct method,conjugate gradient,computer experiment
Conjugate gradient method,Mathematical optimization,CPU time,Direct methods,Hypergraph,Algorithm,Linear programming,Interior point method,Mathematics,Derivation of the conjugate gradient method,Conjugate residual method
Journal
Volume
Issue
ISSN
52
3
0025-5610
Citations 
PageRank 
References 
21
4.49
11
Authors
2
Name
Order
Citations
PageRank
Narendra Karmarkar11670490.93
K. G. Ramakrishnan258798.53