INTERIOR-POINT METHOD AND INDEFINITE SPARSE SOLVER FOR LINEAR-PROGRAMMING PROBLEMS

In 1984, N. Karmarkar at AT&T Bell Labs, proposed a new method of solv ing the linear programming problem. It was claimed that this method, a n interior point method (IPM), would be able to solve certain large-sc ale linear programming problems many times faster on average than the existing Simplex method. Recent studies have indicated that the interi or point methods do seem to offer the computational advantages claimed . Furthermore, tremendous progress has also been made in recent years in developing highly efficient sparse solvers, an essential component of IPM. It is the purpose of this paper to explain a version of IPM an d a version of direct sparse solver which has the capability of solvin g indefinite system of equations that arise from LPM. (C) 1998 Publish ed by Elsevier Science Limited. All rights reserved.