Loading…

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

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 indicates that this algorithm has pote...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 1991-05, Vol.52 (1-3), p.555-586
Main Authors: Karmarkar, N. K., Ramakrishnan, K. G.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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.
ISSN:0025-5610
1436-4646
DOI:10.1007/BF01582905