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.

References in zbMATH (referenced in 36 articles , 1 standard article )

Showing results 1 to 20 of 36.
Sorted by year (citations)

1 2 next

  1. Kanno, Yoshihiro: A fast first-order optimization approach to elastoplastic analysis of skeletal structures (2016)
  2. Dell’Acqua, Pietro; Frangioni, Antonio; Serra-Capizzano, Stefano: Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems (2015)
  3. Dražić, Milan D.; Lazović, Rade P.; Kovačević-Vujčić, Vera V.: Sparsity preserving preconditioners for linear systems in interior-point methods (2015)
  4. Kovács, Péter: Minimum-cost flow algorithms: an experimental evaluation (2015)
  5. Andreani, Roberto; Júdice, Joaquim J.; Martínez, José Mario; Patrício, Joao: A projected-gradient interior-point algorithm for complementarity problems (2011)
  6. Gopalakrishnan, Balaji; Kong, Seunghyun; Barnes, Earl; Johnson, Ellis L.; Sokol, Joel S.: A least-squares minimum-cost network flow algorithm (2011)
  7. Velazco, M.I.; Oliveira, A.R.L.; Campos, F.F.: A note on hybrid preconditioners for large-scale normal equations arising from interior-point methods (2010)
  8. Avron, Haim; Chen, Doron; Shklarski, Gil; Toledo, Sivan: Combinatorial preconditioners for scalar elliptic finite-element problems (2009)
  9. Lu, Zhaosong; Monteiro, Renato D.C.; O’Neal, Jerome W.: An iterative solver-based long-step infeasible primal-dual path-following algorithm for convex QP based on a class of preconditioners (2009)
  10. Portugal, L.F.; Resende, M.G.C.; Veiga, G.; Patrício, J.; Júdice, J.J.: Fortran subroutines for network flow optimization using an interior point algorithm (2008)
  11. Bocanegra, S.; Campos, F.F.; Oliveira, A.R.L.: Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods (2007)
  12. Cafieri, S.; D’Apuzzo, M.; De Simone, V.; di Serafino, D.; Toraldo, G.: Convergence analysis of an inexact potential reduction method for convex quadratic programming (2007)
  13. Frangioni, A.; Gentile, C.: Prim-based support-graph preconditioners for min-cost flow problems (2007)
  14. Frangioni, Antonio; Gentile, Claudio: Experiments with a hybrid interior point/combinatorial approach for network flow problems (2007)
  15. Baryamureeba, Venansius; Steihaug, Trond: On the convergence of an inexact primal-dual interior point method for linear programming (2006)
  16. Lu, Zhaosong; Monteiro, Renato D.C.; O’Neal, Jerome W.: An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming (2006)
  17. Mitchell, John E.; Farwell, Kris; Ramsden, Daryn: Interior point methods for large-scale linear programming (2006)
  18. Mehrotra, Sanjay; Li, Zhifeng: Convergence conditions and Krylov subspace-based corrections for primal-dual interior-point method (2005)
  19. Bellavia, Stefania; Pieraccini, Sandra: Convergence analysis of an inexact infeasible interior point method for semidefinite programming (2004)
  20. Frangioni, A.; Gentile, C.: New preconditioners for KKT systems of network flow problems (2004)

1 2 next