Volume 46, Number 3, July-September 2012
|Page(s)||211 - 234|
|Published online||07 September 2012|
On a dual network exterior point simplex type algorithm and its computational behavior∗
Department of Applied Informatics, University of
Macedonia, 156 Egnatia
2 Department of Technology Management, University of Macedonia, Loggou-Tourpali, 59200 Naoussa, Greece
Accepted: 11 July 2012
The minimum cost network flow problem, (MCNFP) constitutes a wide category of network flow problems. Recently a new dual network exterior point simplex algorithm (DNEPSA) for the MCNFP has been developed. This algorithm belongs to a special “exterior point simplex type” category. Similar to the classical dual network simplex algorithm (DNSA), this algorithm 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 the DNSA, the new algorithm does not always maintain a dual feasible solution. Instead, it produces tree-solutions that can be infeasible for the dual problem and at the same time infeasible for the primal problem. In this paper, we present for the first time, the mathematical proof of correctness of DNEPSA, a detailed comparative computational study of DNEPSA and DNSA on sparse and dense random problem instances, a statistical analysis of the experimental results, and finally some new results on the empirical complexity of DNEPSA. The analysis proves the superiority of DNEPSA compared to DNSA in terms of cpu time and iterations.
Mathematics Subject Classification: 90C27 / 65K05 / 90B10 / 91A90
Key words: Network flows / minimum cost network flow problem / dual network exterior point simplex algorithm
© EDP Sciences, ROADEF, SMAI, 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.