Premium
A truncated primal‐infeasible dual‐feasible network interior point method
Author(s) -
Portugal L. F.,
Resende M. G. C.,
Veiga G.,
Júdice J. J.
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(200003)35:2<91::aid-net1>3.0.co;2-t
Subject(s) - interior point method , solver , conjugate gradient method , mathematical optimization , linear programming , computer science , flow network , iterative method , norm (philosophy) , residual , algorithm , mathematics , political science , law
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 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. © 2000 John Wiley & Sons, Inc.