L.F. Portugal, M.G.C. Resende, G. Veiga, and J.J. Judice

Networks, vol. 35, pp. 91-108, 2000

ABSTRACT

In this paper we introduce the truncated primal-infeasible dual-feasible interior point algorithm for linear programming and describe an implementation of this algorithm for solving the classical minimum cost network flow problem.  In each iteration, the linear system that determines the search direction is computed 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 method 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 cost network flow test problems. Computational results indicate that the implementation is competitive with state-of-the-art network flow codes.

PostScript file of full paper

Go back

Mauricio G.C. Resende's Home Page

Copyright Notice