A dual exterior point simplex type algorithm for the minimum cost network flow problem. Geranis, G., Paparrizos, K., & Sifaleras, A. Yugoslav Journal of Operations Research, 19(1):157--170, 2009.
A dual exterior point simplex type algorithm for the minimum cost network flow problem [link]Paper  abstract   bibtex   
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).
@ARTICLE{GPS2009a,
  author = {G. Geranis and K. Paparrizos and A. Sifaleras},
  title = {A dual exterior point simplex type algorithm for the minimum cost network flow problem},
  journal = {Yugoslav Journal of Operations Research},
  year = {2009},
  volume = {19},
  number = {1},
  pages = {157--170},
	url = {http://dx.doi.org/10.2298/YJOR0901157G},
	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).}
}

Downloads: 0