On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem

V. V. Vasilchikov

Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 4, pp. 401-411

Résumé

The paper describes some ways to accelerate solving the NP-complete Traveling Salesman Problem. The classic Little algorithm belonging to the category of “branch and bound methods” can solve it both for directed and undirected graphs. However, for undirected graphs its operation can be accelerated by eliminating the consideration of branches examined earlier. The paper proposes changes to be made in the key operations of the algorithm to speed up its execution. It also describes the results of an experiment that demonstrated a significant acceleration of solving the problem by using an advanced algorithm. Another way to speed up the work is to parallelize the algorithm. For problems of this kind it is difficult to break the task into a sufficient number of subtasks having comparable complexity. Their parallelism arises dynamically during the execution. For such problems, it seems reasonable to use parallel-recursive algorithms. In our case the use of the library RPM_ParLib developed by the author was a good choice. It allows us to develop effective applications for parallel computing on a local network using any .NET-compatible programming language. We used C# to develop the programs. Parallel applications were developed as for basic and modified algorithms, the comparing of their speed was made. Experiments were performed for the graphs with the number of vertexes up to 45 and with the number of network computers up to 16. We also investigated the acceleration that can be achieved by parallelizing the basic Little algorithm for directed graphs. The results of these experiments are also presented in the paper.

Détail

Keywords: Traveling Salesman Problem, Little algorithm, parallel algorithm, recursion
Mots-clés : .NET.

Bibliographie

[1] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co, San Francisco, 1979 | MR | MR | Zbl

[2] Land A. H., Doig A. G., “An Autmatic Method of Solving Discrete Programming Problems”, Econometrica, 28 (1960), 497–520 | DOI | MR | Zbl

[3] Little J. D. C., Murty K. G., Sweeney D. W., Karel C., “An Algorithm for the Traveling Salesman Problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[4] Kaufmann A., Introduction a la combinatorique en vue des applications, Dunod, Paris, 1968 | MR | MR | Zbl

[5] Reingold E., Nievergelt Ju., Deo N., Combinatorial Algorithms: Theory and Practice, Prentice Hall College, 1977 | MR | MR

[6] Cormen T., Leiserson Ch., Rivest R., Stein C., Introduction to Algorithms, The MIT Press, 2001 | MR

[7] Petrunin S. V., “Ispolzovanie metoda posledovatelnoi separatsii dlya resheniya zadachi kommivoyazhera”, Nauchnyi vestnik MTGU GA, 2009, no. 146, 105–108

[8] Kostyuk Yu. L., “Effektivnaya realizatsiya algoritma resheniya zadachi kommivoyazhera metodom vetvei i granits”, Prikladnaya diskretnaya matematika, 2013, no. 2, 78–90

[9] Sigal I. Kh., Babinskaya Ya. L., Posypkin M. A., “Parallelnaya realizatsiya metoda vetvei i granits v zadache kommivoyazhera na baze biblioteki BNB-Solver”, Trudy ISA RAN, 25 (2006), 26–36

[10] Vasilchikov V. V., Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki, YarGU, Yaroslavl, 2001 (in Russian)

[11] Vasilchikov V. V., Kommunikatsionnyi modul dlya organizatsii polnosvyaznogo soedineniya kompyuterov v lokalnoi seti s ispolzovaniem .NET Framework, Svidetelstvo o gosudarstvennoi registratsii programmy dlya EVM # 2013619925, 2013

[12] Vasilchikov V. V., Biblioteka podderzhki rekursivno-parallelnogo programmirovaniya dlya .NET Framework, Svidetelstvo o gosudarstvennoi registratsii programmy dlya EVM # 2013619926, 2013

[13] Vasilchikov V. V., “On the Recursive-Parallel Programming for the .NET Framework”, Modeling and Analysis of Information Systems, 21:2 (2014), 15–25 (in Russian)