A truncated primal-infeasible dual-feasible network interior point method

In this paper, we introduce the truncated primal-infeasible dual-feasible i nterior point algorithm for linear programming and describe an implementati on of this algorithm for solving the minimum-cost network flow problem. In each iteration, the linear system that determines the search direction is c omputed inexactly, and the norm of the resulting residual vector is used in the stopping criteria of the iterative solver employed for the solution of the system. In the implementation, a preconditioned conjugate gradient met hod is used as the iterative solver. The details of the implementation are described and the code PDNET is tested on a large set of standard minimum-c ost network flow test problems. Computational results indicate that the imp lementation is competitive with state-of-the-art network flow codes. (C) 20 00 John Wiley & Sons, Inc.