A dual network exterior point simplex-type algorithm for the minimum cost network flow problem

Abstract

The Minimum Cost Network Flow Problem (MCNFP) refers to a wide category of network flow problems and it is an important research area of Network Optimization. A Dual Network Exterior Point Simplex Algorithm (DNEPSA) for the MCNFP is presented here. The algorithm belongs to the special category of Exterior Point Simplex-Type algorithms. Similarly to the classical Dual Network Simplex-type Algorithm (DNSA), DNEPSA starts with a dual feasible tree-solution and after a number of iterations, it produces a solution that is both primal and dual feasible, i.e. it is optimal. However, contrary to DNSA, the algorithm does not always maintain a dual feasible solution throughout all its iterations. Instead, it produces tree-solutions that can be infeasible for the dual problem and at the same time infeasible for the primal problem. The theoretical proof of correctness and the implementation details of DNEPSA are also presented. A detailed comparative computational study of DNEPSA against DNSA on sparse and dense random problem instances is presented and it is followed by the statistical analysis of the experimental results showing the effectiveness of DNEPSA compared to DNSA in terms of cpu time and iterations. The implementation of DNEPSA by using dynamic trees is also demonstrated and the algorithm’s amotized computational complexity per pivot is estimated.