On a dual network exterior point simplex type algorithm and its computational behavior

George Geranis; Konstantinos Paparrizos; Angelo Sifaleras

RAIRO - Operations Research - Recherche Opérationnelle (2012)

  • Volume: 46, Issue: 3, page 211-234
  • ISSN: 0399-0559

Abstract

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

How to cite

top

Geranis, George, Paparrizos, Konstantinos, and Sifaleras, Angelo. "On a dual network exterior point simplex type algorithm and its computational behavior." RAIRO - Operations Research - Recherche Opérationnelle 46.3 (2012): 211-234. <http://eudml.org/doc/275029>.

@article{Geranis2012,
abstract = {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.},
author = {Geranis, George, Paparrizos, Konstantinos, Sifaleras, Angelo},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {network flows; minimum cost network flow problem; dual network exterior point simplex algorithm},
language = {eng},
number = {3},
pages = {211-234},
publisher = {EDP-Sciences},
title = {On a dual network exterior point simplex type algorithm and its computational behavior},
url = {http://eudml.org/doc/275029},
volume = {46},
year = {2012},
}

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
PB - EDP-Sciences
VL - 46
IS - 3
SP - 211
EP - 234
AB - 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.
LA - eng
KW - network flows; minimum cost network flow problem; dual network exterior point simplex algorithm
UR - http://eudml.org/doc/275029
ER -

References

top
  1. [1] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows : theory, algorithms and applications. Prentice Hall, Englewood Cliffs, NJ (1993). Zbl1201.90001MR1205775
  2. [2] R.K. Ahuja, T.L. Magnanti, J.B. Orlin and M. Reddy, Applications of network optimization. Handbooks of Operations Research and Management Science7 (1995) 1–83. Zbl0833.90116MR1420866
  3. [3] D. Andreou, K. Paparrizos, N. Samaras and A. Sifaleras, Visualization of the network exterior primal simplex algorithm for the minimum cost network flow problem. Oper. Res.7 (2007) 449–464. Zbl1299.90003
  4. [4] Th. Baloukas, K. Paparrizos and A. Sifaleras, An animated demonstration of the uncapacitated network simplex algorithm. ITE10 (2009) 34–40. 
  5. [5] D.P. Bertsekas and P. Tseng, 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. [6] S. Chakraborty and P.P. Choudhury, A statistical analysis of an algorithm’s complexity. Appl. Math. Lett.13 (2000) 121–126. Zbl0965.68139MR1760273
  7. [7] M. Coffin and M.J. Saltzman, Statistical Analysis of computational tests of algorithms and heuristics. INFORMS J. Comput.12 (2000) 24–44. Zbl1034.90020
  8. [8] C. Cotta and P. Moscato, A mixed evolutionary-statistical analysis of an algorithm’s complexity. Appl. Math. Lett.16 (2003) 41–47. Zbl1081.68012
  9. [9] T.R. Ervolina and S.T. McCormick, Two strongly polynomial cut canceling algorithms for minimum cost network flow. Discr. Appl. Math.46 (1993) 133–165. Zbl0801.90037MR1241076
  10. [10] M. Fredman and R. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM34 (1987) 596–615. MR904195
  11. [11] K. Fukuda and T. Terlaky, Criss-cross methods : a fresh view on pivot algorithms. Math. Program.79 (1997) 369–395. Zbl0887.90113MR1464775
  12. [12] G. Geranis, K. Paparrizos and A. Sifaleras, A dual exterior point simplex type algorithm for the minimum cost network flow problem. Yugosl. J. Oper. Res.19 (2009) 157–170. Zbl1274.90457MR2535052
  13. [13] G. Geranis, K. Paparrizos and A. Sifaleras, 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). Zbl1254.90032
  14. [14] F. Glover, D. Klingman and A. Napier, Basic dual feasible solutions for a class of generalized networks. Oper. Res.20 (1972) 126–136. Zbl0238.90074MR314564
  15. [15] F. Glover, D. Karney and D. Klingman, The augmented predecessor index method for locating stepping stone paths and assigning dual prices in distribution problems. Transp. Sci.6 (1972) 171–180. 
  16. [16] F. Glover, D. Klingman and N. Phillips, Network models in optimization and their applications in practice. Wiley Publications (1992). 
  17. [17] A.V. Goldberg, An Efficient Implementation of a scaling minimum-cost flow algorithm. J. Algorithms22 (1997) 1–29. Zbl0924.90061MR1425307
  18. [18] A. Goldberg, M. Grigoriadis and R.E. Tarjan, Use of dynamic trees in a network simplex algorithm for the maximum flow problem, Math. Program.50 (1991) 277–290. Zbl0743.90107MR1114233
  19. [19] M. Grigoriadis, An efficient implementation of the network simplex method. Math. Program. Stud.26 (1984) 83–111. Zbl0594.90025MR830487
  20. [20] J. Hultz and D. Klingman, An advanced dual basic feasible solution for a class of capacitated generalized networks. Oper. Res.24 (1976) 301–313. Zbl0362.90124MR416604
  21. [21] J. Kennington and R. Helgason, Algorithms for network programming. Wiley, New York (1980). Zbl0502.90056MR581251
  22. [22] D. Klingman, A. Napier and J. Stutz, NETGEN : a program for generating large scale capacitated assignment, transportation, and minimum cost flow networks. Manag. Sci.20 (1974) 814–821. Zbl0303.90042MR329614
  23. [23] I. Maros, A practical anti-degeneracy row selection technique in network linear programming. Ann. Oper. Res.47 (1993) 431–442. Zbl0786.90040MR1260031
  24. [24] C.C. McGeoch, Toward an experimental method for algorithm simulation. INFORMS J. Comput.8 (1996) 1–15. Zbl0854.68038
  25. [25] R. Nance, R. Moose and R. Foutz, A statistical technique for comparing heuristics : an example from capacity assignment strategies in computer network design. Commun. ACM30 (1987) 430–442. 
  26. [26] J.B. Orlin, 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). MR803324
  27. [27] K. Paparrizos, N. Samaras and A. Sifaleras, An exterior simplex type algorithm for the minimum cost network flow problem. Comput. Oper. Res.36 (2009) 1176–1190. Zbl1162.90547MR2579759
  28. [28] M. Resende and G. Veiga, 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. Zbl0787.90028
  29. [29] R.E. Tarjan, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program.78 (1997) 169–177. Zbl0889.90150MR1486308
  30. [30] R. Vanderbei, Linear programming : foundations and extensions, 3rd edition. Springer, New York (2007). Zbl1299.90243MR3100219
  31. [31] N. Zadeh, More pathological examples for network flow problems. Math. Program.5 (1973) 217–224. Zbl0272.90081MR363441
  32. [32] N. Zadeh, A bad network problem for the simplex method and other minimum cost flow algorithms. Math. Programm.5 (1973) 255–266. Zbl0287.90030MR343880

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.