The minimum cost network flow problem, (MCNFP) constitutes a wide category of network flow problems. Recently a new dual network exterior point simplex algorithm (DNEPSA) for the MCNFP has been developed. This algorithm belongs to a special “exterior point simplex type” category. Similar to the classical dual network simplex algorithm (DNSA), this algorithm starts with a dual feasible tree-solution and after a number of iterations, it produces a solution that is both primal and dual feasible, i.e. it is optimal. However, contrary to the DNSA, the new algorithm does not always maintain a dual feasible solution. Instead, it produces tree-solutions that can be infeasible for the dual problem and at the same time infeasible for the primal problem. In this paper, we present for the first time, the mathematical proof of correctness of DNEPSA, a detailed comparative computational study of DNEPSA and DNSA on sparse and dense random problem instances, a statistical analysis of the experimental results, and finally some new results on the empirical complexity of DNEPSA. The analysis proves the superiority of DNEPSA compared to DNSA in terms of cpu time and iterations.
Mots-clés : network flows, minimum cost network flow problem, dual network exterior point simplex algorithm
@article{RO_2012__46_3_211_0,
author = {Geranis, George and Paparrizos, Konstantinos and Sifaleras, Angelo},
title = {On a dual network exterior point simplex type algorithm and its computational behavior},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {211--234},
publisher = {EDP-Sciences},
volume = {46},
number = {3},
year = {2012},
doi = {10.1051/ro/2012015},
mrnumber = {2989084},
zbl = {1254.90032},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2012015/}
}
TY - JOUR AU - Geranis, George AU - Paparrizos, Konstantinos AU - Sifaleras, Angelo TI - On a dual network exterior point simplex type algorithm and its computational behavior JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2012 SP - 211 EP - 234 VL - 46 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2012015/ DO - 10.1051/ro/2012015 LA - en ID - RO_2012__46_3_211_0 ER -
%0 Journal Article %A Geranis, George %A Paparrizos, Konstantinos %A Sifaleras, Angelo %T On a dual network exterior point simplex type algorithm and its computational behavior %J RAIRO - Operations Research - Recherche Opérationnelle %D 2012 %P 211-234 %V 46 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2012015/ %R 10.1051/ro/2012015 %G en %F RO_2012__46_3_211_0
Geranis, George; Paparrizos, Konstantinos; Sifaleras, Angelo. On a dual network exterior point simplex type algorithm and its computational behavior. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 3, pp. 211-234. doi : 10.1051/ro/2012015. http://www.numdam.org/articles/10.1051/ro/2012015/
[1] , and , Network flows : theory, algorithms and applications. Prentice Hall, Englewood Cliffs, NJ (1993). | MR | Zbl
[2] , , and , Applications of network optimization. Handbooks of Operations Research and Management Science 7 (1995) 1-83. | MR | Zbl
[3] , , and , Visualization of the network exterior primal simplex algorithm for the minimum cost network flow problem. Oper. Res. 7 (2007) 449-464. | Zbl
[4] , and , An animated demonstration of the uncapacitated network simplex algorithm. ITE 10 (2009) 34-40.
[5] and , RELAX-IV : A faster version of the RELAX code for solving minimum cost flow problems. Technical Report, Massachusetts Institute of Technology, Laboratory for Information and Decision Systems (1994).
[6] and , A statistical analysis of an algorithm's complexity. Appl. Math. Lett. 13 (2000) 121-126. | MR | Zbl
[7] and , Statistical Analysis of computational tests of algorithms and heuristics. INFORMS J. Comput. 12 (2000) 24-44. | Zbl
[8] and , A mixed evolutionary-statistical analysis of an algorithm's complexity. Appl. Math. Lett. 16 (2003) 41-47. | Zbl
[9] and , Two strongly polynomial cut canceling algorithms for minimum cost network flow. Discr. Appl. Math. 46 (1993) 133-165. | MR | Zbl
[10] and , Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34 (1987) 596-615. | MR
[11] and , Criss-cross methods : a fresh view on pivot algorithms. Math. Program. 79 (1997) 369-395. | MR | Zbl
[12] , and , A dual exterior point simplex type algorithm for the minimum cost network flow problem. Yugosl. J. Oper. Res. 19 (2009) 157-170. | MR | Zbl
[13] , and , On the Computational Behavior of a Dual Network Exterior Point Simplex Algorithm for the Minimum Cost Network Flow Problem, in Proceedings of the International Network Optimization Conference (INOC 2009). Pisa, Italy (2009).
[14] , and , Basic dual feasible solutions for a class of generalized networks. Oper. Res. 20 (1972) 126-136. | MR | Zbl
[15] , and , The augmented predecessor index method for locating stepping stone paths and assigning dual prices in distribution problems. Transp. Sci. 6 (1972) 171-180.
[16] , and , Network models in optimization and their applications in practice. Wiley Publications (1992).
[17] , An Efficient Implementation of a scaling minimum-cost flow algorithm. J. Algorithms 22 (1997) 1-29. | MR | Zbl
[18] , and , Use of dynamic trees in a network simplex algorithm for the maximum flow problem, Math. Program. 50 (1991) 277-290. | MR | Zbl
[19] , An efficient implementation of the network simplex method. Math. Program. Stud. 26 (1984) 83-111. | MR | Zbl
[20] and , An advanced dual basic feasible solution for a class of capacitated generalized networks. Oper. Res. 24 (1976) 301-313. | MR | Zbl
[21] and , Algorithms for network programming. Wiley, New York (1980). | MR | Zbl
[22] , and , NETGEN : a program for generating large scale capacitated assignment, transportation, and minimum cost flow networks. Manag. Sci. 20 (1974) 814-821. | MR | Zbl
[23] , A practical anti-degeneracy row selection technique in network linear programming. Ann. Oper. Res. 47 (1993) 431-442. | MR | Zbl
[24] , Toward an experimental method for algorithm simulation. INFORMS J. Comput. 8 (1996) 1-15. | Zbl
[25] , and , A statistical technique for comparing heuristics : an example from capacity assignment strategies in computer network design. Commun. ACM 30 (1987) 430-442.
[26] , Genuinely polynomial simplex and non-simplex algorithms for the minimum cost flow problem. Technical Report No. 1615-84, Sloan School of Management, M.I.T., Cambridge, MA (1984). | MR
[27] , and , An exterior simplex type algorithm for the minimum cost network flow problem. Comput. Oper. Res. 36 (2009) 1176-1190. | MR | Zbl
[28] and , An efficient implementation of a network interior point method, in Network flows and matching : first DIMACS implementation challenge 12, edited by D.S. Johnson and C.C. McGeoch. DIMACS series in discrete mathematics and theoretical computer science, American Mathematical Society, Providence, Rhode Island (1993) 299-348. | Zbl
[29] , Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program. 78 (1997) 169-177. | MR | Zbl
[30] , Linear programming : foundations and extensions, 3rd edition. Springer, New York (2007). | MR | Zbl
[31] , More pathological examples for network flow problems. Math. Program. 5 (1973) 217-224. | MR | Zbl
[32] , A bad network problem for the simplex method and other minimum cost flow algorithms. Math. Programm. 5 (1973) 255-266. | MR | Zbl
Cité par Sources :
