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 Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Fortran subroutines for network flow optimization using an interior point algorithm. Zbl 1257.90107Portugal, L. F.; Resende, M. G. C.; Veiga, G.; Patrício, J.; Júdice, J. J. 2008 all top 5 Cited by 68 Authors 6 Frangioni, Antonio 5 Júdice, Joaquim João 5 Resende, Mauricio G. C. 4 Portugal, Luis F. 3 Gentile, Claudio 3 Serra-Capizzano, Stefano 3 Veiga, Geraldo 3 Wang, Weichung 2 Baryamureeba, Venansius 2 Bellavia, Stefania 2 Campos, Frederico F. 2 Dell’Acqua, Pietro 2 Jarre, Florian 2 Lu, Zhaosong 2 Mehrotra, Sanjay 2 Mizuno, Shinji 2 Monteiro, Renato D. C. 2 O’Leary, Dianne P. 2 Oliveira, Aurelio Ribeiro Leite 2 O’Neal, Jerome W. 2 Patricio, João 2 Steihaug, Trond 1 Andreani, Roberto 1 Avron, Haim 1 Barnes, Earl R. 1 Bocanegra, Silvana 1 Bonnans, Joseph Frédéric 1 Cafieri, Sonia 1 Castro, Jordi 1 Chen, Doron 1 Cui, Yiran 1 D’Apuzzo, Marco 1 De Simone, Valentina 1 di Serafino, Daniela 1 Dražić, Milan D. 1 El Ghami, Mohamed 1 Farwell, Kris 1 Figueira, José Rui 1 Fonseca, Margarida 1 Freund, Roland W. 1 Gopalakrishnan, Balaji 1 Hayami, Ken 1 Johnson, Ellis L. 1 Kanno, Yoshihiro 1 Karisch, Stefan E. 1 Kong, Seunghyun 1 Kovačević-Vujčić, Vera V. 1 Kovács, Peter 1 Lazović, Rade P. 1 Li, Zhifeng 1 Martínez, José Mario 1 Mitchell, John E. 1 Morikuni, Keiichi 1 Pardalos, Panos M. 1 Pieraccini, Sandra 1 Pola, Cecilia 1 Ramsden, Daryn 1 Rébai, Raja 1 Rendl, Franz 1 Shklarski, Gil 1 Sokol, Joel S. 1 Toledo, Sivan 1 Toraldo, Gerardo 1 Tsuchiya, Takashi 1 Velazco, M. I. 1 Wang, Jen-Shan 1 Wolkowicz, Henry 1 Zhao, Qing all top 5 Cited in 21 Serials 6 Computational Optimization and Applications 5 Optimization Methods & Software 4 SIAM Journal on Optimization 2 Journal of Optimization Theory and Applications 2 SIAM Journal on Matrix Analysis and Applications 2 Numerical Algorithms 1 Computers & Mathematics with Applications 1 Journal of the Australian Mathematical Society, Series B 1 Applied Mathematics and Computation 1 Calcolo 1 Journal of Computational and Applied Mathematics 1 Mathematics of Operations Research 1 Networks 1 Computers & Operations Research 1 Annals of Operations Research 1 Mathematical Programming. Series A. Series B 1 Revista Investigación Operacional 1 International Transactions in Operational Research 1 Journal of Combinatorial Optimization 1 Optimization and Engineering 1 Pesquisa Operacional all top 5 Cited in 7 Fields 37 Operations research, mathematical programming (90-XX) 13 Numerical analysis (65-XX) 2 Combinatorics (05-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 1 Partial differential equations (35-XX) 1 Mechanics of deformable solids (74-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year