Voir la notice de l'article provenant de la source Numdam
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.
@article{RO_2012__46_3_211_0,
author = {Geranis, George and Paparrizos, Konstantinos and Sifaleras, Angelo},
title = {On a dual network exterior point simplex type algorithm and its computational behavior},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {211--234},
publisher = {EDP-Sciences},
volume = {46},
number = {3},
year = {2012},
doi = {10.1051/ro/2012015},
mrnumber = {2989084},
zbl = {1254.90032},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2012015/}
}
TY - JOUR AU - Geranis, George AU - Paparrizos, Konstantinos AU - Sifaleras, Angelo TI - On a dual network exterior point simplex type algorithm and its computational behavior JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2012 SP - 211 EP - 234 VL - 46 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2012015/ DO - 10.1051/ro/2012015 LA - en ID - RO_2012__46_3_211_0 ER -
%0 Journal Article %A Geranis, George %A Paparrizos, Konstantinos %A Sifaleras, Angelo %T On a dual network exterior point simplex type algorithm and its computational behavior %J RAIRO - Operations Research - Recherche Opérationnelle %D 2012 %P 211-234 %V 46 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2012015/ %R 10.1051/ro/2012015 %G en %F RO_2012__46_3_211_0
Geranis, George; Paparrizos, Konstantinos; Sifaleras, Angelo. On a dual network exterior point simplex type algorithm and its computational behavior. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 3, pp. 211-234. doi: 10.1051/ro/2012015
Cité par Sources :