A dual exterior point simplex type algorithm for the minimum cost network flow problem
DOI:
https://doi.org/10.2298/YJOR0901157GKeywords:
Operations research, combinatorial optimization, minimum cost network flow problemAbstract
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).References
Ahuja, R., Magnanti, T., Orlin, J., Reddy, M. (1995) Applications of network optimization. u: Handbooks of Operations Research and Management Science, 1-83
Ahuja, R., Orlin, J. (1988) Improved primal simplex algorithms for shortest path, assignment and minimum cost flow problems. Massachusetts Institute of Technology, Operations Research Center, Working Paper OR 189-88
Ali, A.I., Helgason, R.V., Kennington, J.L., Lall, H.S. (1978) Primal simplex network codes: State-of-the-art implementation technology. Networks, 8(4): 315
Bertsekas, D.P., Tseng, P. (1994) RELAX-IV: A faster version of the RELAX code for solving minimum cost flow problems. Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, Technical Report
Eppstein, D. (1994) Clustering for faster network simplex pivots. u: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms
Fredman, M., Tarjan, R. (1987) Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3): 596
Glover, F., Karney, D., Klingman, D. (1974) Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems. Networks, 4(3): 191
Glover, F., Klingman, D., Napier, A. (1972) Basic dual feasible solutions for a class of generalized networks. Operations Research, 20(1): 126
Glover, F., Klingman, D., Phillips, N. (1992) Network models in optimization and their applications in practice. Wiley Publications
Goldberg, A., Grigoriadis, M., Tarjan, R. (1991) Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Mathematical Programming, 50(1-3): 277
Hultz, J., Klingman, D. (1976) An advanced dual basic feasible solution for a class of capacitated generalized networks. Operations Research, 24 (2)
Karagiannis, P., Markelis, I., Paparrizos, K., Samaras, N., Sifaleras, A. (2006) E - learning technologies: Employing matlab web server to facilitate the education of mathematical programming. International Journal of Mathematical Education in Science and Technology, 37 (7) 765-782., Taylor & Francis Publications
Karagiannis, P., Paparrizos, K., Samaras, N., Sifaleras, A. (2005) A new simplex type algorithm for the minimum cost network flow problem. u: Balkan Conference on Operational Research, (7th), Proceedings, 133-139
Kennington, J.L., Helgason, R.V. (1980) Algorithms for network programming. Wiley Publications
Orlin, J.B. (1984) Genuinely polynomial simplex and non-simplex algorithms for the minimum cost flow problem. Cambridge, MA: Sloan School of Management, Technical Report No. 1615-84
Tarjan, R.E. (1997) Dynamic trees as search trees via euler tours, applied to the network simplex algorithm. Mathematical Programming, 78(2): 169
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
