Please use this identifier to cite or link to this item:
Title: On a dual network exterior point simplex type algorithm and its computational behavior
Authors: Geranis, George
Paparrizos, Konstantinos
Sifaleras, Angelo
Type: Article
Subjects: FRASCATI::Natural sciences::Mathematics::Applied Mathematics
FRASCATI::Natural sciences::Computer and information sciences
Keywords: Network flows
Minimum cost network flow problem
Dual network exterior point simplex algorithm
Issue Date: 2012
Publisher: EDP Sciences
Source: RAIRO - Operations Research
Volume: 46
Issue: 3
First Page: 211
Last Page: 234
Abstract: 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.
ISSN: 0399-0559
Other Identifiers: 10.1051/ro/2012015
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
On_a_dual_network_exterior_point_simplex_type_algorithm_and_its_computational_behavior.pdf678,7 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.