A modified Schur complement method for handling dense columns
in interior point methods for linear programming
Knud D. Andersen
The main computational work in interior point methods for linear
programming (LP) is to find a solution of a least squares
problem. Usually this is solved using the normal-equations approach.
However, if the LP constraint matrix contains a nearly dense column
the normal equations will be nearly dense. Consequently for large
sparse LP problems it will be extremely expensive to solve the normal
equations. In this paper we propose a modified Schur-complement method
to handle dense columns which has some desirable properties compared
to the original Schur complement method. Encouraging numerical results
are presented.
![[DVI]](../../InteriorPoint/gif/DVI.gif)
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)