On a dual network exterior point simplex type algorithm and its computational behavior

Autor:	Konstantinos Paparrizos, Angelo Sifaleras, George Geranis
Rok vydání:	2012
Předmět:	Mathematical optimization Simplex CPU time Management Science and Operations Research Flow network Mathematical proof Computer Science Applications Theoretical Computer Science Dual (category theory) Simplex algorithm Point (geometry) Minimum-cost flow problem Algorithm Mathematics
Zdroj:	RAIRO - Operations Research. 46:211-234
ISSN:	1290-3868 0399-0559
DOI:	10.1051/ro/2012015
Popis:	The minimum cost network flow problem, (MCNFP) con- stitutes 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 al- gorithm (DNSA), this algorithm starts with a dual feasible tree-solution and after a number of iterations, it produces a solution that is both pri- mal 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 cor- rectness 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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::259d92c9eba57e86c3a373bc1f1958e8 https://doi.org/10.1051/ro/2012015 Zobrazit plný text záznamu