×

PDNET

swMATH ID: 4752
Software Authors: Portugal, L.F.; Resende, M.G.C.; Veiga, G.; Júdice, J.J.
Description: A truncated primal-infeasible dual-feasible network interior point method The authors 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.
Homepage: http://mauricio.resende.info/pdnet/
Keywords: interior point method; linear programming; network flows; primal-infeasible dual-feasible; truncated Newton method; conjugate gradient; maximum flow; experimental testing of algorithms
Related Software: DIMACS; PCx; IPM; RelaxIV; CPLEX; NETGEN; QAPLIB; TAUCS; LIPSOL; HOPDM; PATH Solver; RELAX4; MCFClass; MINOS; LOQO; LAPACK; KORBX; CSparse; PDCO; SparseMatrix
Cited in: 40 Publications

Citations by Year