A dual exterior point simplex type algorithm for the minimum cost network flow problem

A dual exterior point simplex type algorithm for the minimum cost network flow problem

0.00 Avg rating0 Votes
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: , ,
Keywords: networks: flow
Abstract:

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).

Reviews

Required fields are marked *. Your email address will not be published.