Please use this identifier to cite or link to this item:
Title: An exterior simplex type algorithm for the Minimum Cost Network Flow Problem
Authors: Paparrizos, Konstantinos
Samaras, Nikolaos
Sifaleras, Angelo
Type: Article
Subjects: FRASCATI::Natural sciences::Mathematics::Applied Mathematics
FRASCATI::Natural sciences::Computer and information sciences
Keywords: Combinatorial optimization
Minimum Cost Network Flow Problem
Simplex algorithm
Exterior point algorithm
Issue Date: 2009
Publisher: Elsevier
Source: Computers & Operations Research
Volume: 36
Issue: 4
First Page: 1176
Last Page: 1190
Abstract: In this paper a new Network Exterior Point Simplex Algorithm (NEPSA) for the Minimum Cost Network Flow Problem (MCNFP) is analytically presented. NEPSA belongs to a special simplex type category and is a modification of the classical network simplex algorithm. The main idea of the algorithm is to compute two flows. One flow is basic but not always feasible and the other is feasible but not always basic. A complete proof of correctness for the proposed algorithm is also presented. Moreover, the computational behavior of NEPSA is shown by an empirical study carried out for randomly generated sparse instances created by the well-known GRIDGEN network problem generator.
ISSN: 03050548
Other Identifiers: 10.1016/j.cor.2008.01.001
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
An_exterior_Simplex_type_algorithm_for_the_minimum_cost_network_flow_problem.pdf238,88 kBAdobe PDFView/Open

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