Computational results of an interior point algorithm for large scale linear programming

Computational results of an interior point algorithm for large scale linear programming

0.00 Avg rating0 Votes
Article ID: iaor19921515
Country: Netherlands
Volume: 52
Issue: 3
Start Page Number: 555
End Page Number: 586
Publication Date: Dec 1991
Journal: Mathematical Programming
Authors: ,
Keywords: interior point methods
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. The present computational experience reported here 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. It has conducted extensive computational experiments on problems representative of large classes of applications of current interest. The paper has 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 the implementation with MINOS 5.1 shows that the present implementation is orders of magnitude faster than MINOS 5.1 for these problems.

Reviews

Required fields are marked *. Your email address will not be published.