Article ID: | iaor200970211 |
Country: | Serbia |
Volume: | 19 |
Issue: | 1 |
Start Page Number: | 157 |
End Page Number: | 170 |
Publication Date: | Jan 2009 |
Journal: | Yugoslav Journal of Operations Research |
Authors: | Geranis George, Paparizzos Konstantinos, Sifaleras Angelo |
Keywords: | networks: flow |
A new dual simplex type algorithm for the Minimum Cost Network Flow Problem (MCNFP) is presented. The proposed algorithm belongs to a special ‘exterior-point simplex type’category. Similarly to the classical network dual simplex algorithm (NDSA), this algorithm starts with a dual feasible tree-solution and reduces the primal infeasibility, iteration by iteration. However, contrary to the NDSA, the new algorithm does not always maintain a dual feasible solution. Instead, the new algorithm might reach a basic point (tree-solution) outside the dual feasible area (exterior point - dual infeasible tree).