An exterior simplex type algorithm for the Minimum Cost Network Flow Problem |
| |
Authors: | Konstantinos Paparrizos Nikolaos Samaras Angelo Sifaleras |
| |
Affiliation: | Department of Applied Informatics, University of Macedonia, 156 Egnatia Street, Thessaloniki 54006, Greece |
| |
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. |
| |
Keywords: | 90C27 90C49 90C35 65K05 91A90 |
本文献已被 ScienceDirect 等数据库收录! |