|Article title||POLYNOMIAL COMPLEXITY OF THE PARALLEL FORM OF THE BRANCH AND BORDERS METHOD FOR SOLVING THE COMMIS VOYAGEUR’S PROBLEM|
|Authors||Ya.E. Romm, E.G. Nazaryants|
|Section||SECTION I. MODELING AND DESIGN|
|Month, Year||04, 2015 @en|
|Index UDC||681.3.06: 681.323(519.6)|
|Abstract||The work contains the parallel transformation of George Little algorithm of the implementation of branch and borders method for solving the commis voyageur’s problem based on the identification of extremums using maximum parallel sorting by counting on comparisons’ matrixes. There are the description and the program of sorting with the estimation of time complexity. The method and programmatic operators of the local extremums identification, that are realizing it, are described in the work. The proposed parallel algorithm is cyclical, there are given two estimations of its time complexity T(n4/6-n3/4)=O(nlog2n) for T(n4/6-n3/4)=O(n5 log2n) for cases without returning to the ragged branches and with returning to one of them (excluding investments). In the simultaneous processing of all ragging branches excluding investment, the time complexity in the comparing with treating of one ragged branch does not increase due to growth of the processors’ number, and we have the estimation T(n6/6)=O(n5log2n). Estimates based on the number of processors have been used an abstract model of straight-line parallel programs, wherein it does not take into account the architecture of the parallel computing system and the exchange’s time. The numerical simulation of the proposed parallel algorithm is done with using its consistent implementation on a personal computer. The results of numerical experiments which confirm the correct operation of the proposed parallel George Little algorithm’s modification are introduced. There are given the comparison of the results with the known results of applying different algorithms and the programs of parallel implementation of the branch and borders method for solving the commis voyageur’s problem. The essential difference between the proposed method of solving the commis voyageur’s problem from the known methods is a association of parallel sorting and strictly speaking method of branches and borders, providing to get an estimation of polynomial time complexity of algorithm.|
|Keywords||The commis voyageur’s problem; a parallel form of the branch and borders method; the polynomial estimation of time complexity of algorithm; parallel sorting by counting.|
|References||1. Sergienko I.V., Emets O.A., Emets A.O. Zadachi optimizatsii s interval'noy neopredelennost'yu: metod vetvey i granits [Задачи оптимизации с интервальной неопределенностью: метод ветвей и границ], Kibernetika i sistemnyy analiz [Cybernetics and Systems Analysis], 2013, No. 5, pp. 38-51.
2. Ovezgel'dyev A.O., Morozov A.V. Razvitie metoda vetvey i granits v zadache poiska optimal'nogo kol'tsevogo marshruta [Development of a method of branches and boundaries in the problem of finding the optimal ring route], Kibernetika i sistemnyy analiz [Cybernetics and Systems Analysis], 2013, No. 5, pp. 112-124.
3. Gaurav Bhardwaj, Manish Pandey. Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU, International Journal of Computer Applications, August 2014, Vol. 99, No. 16, pp. 9-13.
4. Gaurav Bhardwaj, Manish Pandey. Parallel Implementation of Travelling Salesman Problem using Ant Colony Optimization, International Journal of Computer Applications Technology and Research, 2014, Vol. 3, Issue 6, pp. 385-389.
5. Little J., Murty K., Sweeney D., Karel C. An algorithm for the travelling salesman problem, Operations research, 1963, Vol. 11, pp. 972-989.
6. Wirth N. Algorithms and Data Structures, August 2004, pp. 183.
7. Romm Ya.E., Nazar'yants E.G. Preobrazovanie metoda vetvey i granits dlya resheniya zadachi kommivoyazhera na osnove maksimal'no parallel'noy sortirovki [The transformation method of branch and bound for solving the travelling salesman problem on the basis of maximum parallel sorting]. Taganrog: TGPI., 2013, 25 p. Dep. v VINITI 30.09.2013, No. 279-V2013.
8. Solodovnikov V.I. Verkhnie otsenki slozhnosti resheniya sistem lineynykh uravneniy [Upper bounds on the complexity of solving systems of linear equations], V kn.: Teoriya slozhnosti vychisleniy. I: Zapiski nauchnykh seminarov LOMI AN SSSR [In the book: The theory of computational complexity. I: notes of scientific seminars of LOMI an SSSR]. Leningrad, 1982, Vol. 118, pp. 159-187.
9. Gavrilkevich M.V., Solodovnikov V.I. Effektivnye algoritmy resheniya zadach lineynoy algebry nad polem iz dvukh elementov [Efficient algorithms for solving problems of linear algebra over the field of two elements], Obozrenie prikladnoy i promyshlennoy matematiki [Review of Applied and Industrial Mathematics], 1995, Vol. 2, No. 3, pp. 399-439.
10. Romm Ya.E. Parallel'naya sortirovka sliyaniem po matritsam sravneniy. I [Parallel merge sort on a matrix of comparisons. I], Kibernetika i sistemnyy analiz [Cybernetics and Systems Analysis], 1994, No. 5, pp. 3-23.
11. Romm Ya.E. Parallel'naya sortirovka sliyaniem po matritsam sravneniy. II [Parallel merge sort on a matrix of comparisons. I], Kibernetika i sistemnyy analiz [Cybernetics and Systems Analysis], 1994, No. 5, pp. 13-37.
12. Romm Ya.E., Zaika I.V. Chislennaya optimizatsiya na osnove algoritmov sortirovki s prilozheniem k differentsial'nym i nelineynym uravneniyam obshchego vida [Numerical optimization-based sorting algorithms with applications to differential and non-linear equations of the General form], Kibernetika i sistemnyy analiz [Cybernetics and Systems Analysis], 2011,
No. 2, pp. 165-180.
13. Romm Ya.E., Dzyuba A.S., Nazar'yants E.G. Preobrazovanie i chislennoe modelirovanie metoda vetvey i granits dlya resheniya zadachi kommivoyazhera na osnove maksimal'no parallel'noy sortirovki [Transformation and numerical simulation method of branch and bound for solving the travelling salesman problem on the basis of maximum parallel sorting]. Taganrog: TGPI, 2014, 49 p. Dep. v VINITI 30.09.2014, No. 279-V2013.
14. Kolpakov R.M., Posypkin M.A., Sigal I.Kh. O nizhney otsenke vychislitel'noy slozhnosti odnoy parallel'noy realizatsii metoda vetvey i granits [On the lower bound computational complexity of a parallel implementation of the method of branches and borders], Avtomatika i telemekhanika [Automation and Remote Control], 2010, No. 10, pp. 156-166.
15. Richard Wiener. Branch and Bound Implementations for the Traveling Salesperson Problem, Journal of Object Technology, March-April 2003, Part. 1, No. 2, pp. 65-86.
16. Leo Liberti. Branch-and-Bound for the Travelling Salesman Problem, LIX, Ecole Polytechnique, F-91128 Palaiseau, March 15, 2011. – pp. 1-8.
17. Posypkin M.A, Sigal I.Kh. Verkhnyaya otsenka dlya uskoreniya v odnoy parallel'noy realizatsii metoda vetvey i granits resheniya zadach diskretnoy optimizatsii [An upper bound for the acceleration in a parallel implementation of the method of branch and bound for solving discrete optimization], Trudy tret'ey mezhdunarodnoy konferentsii «parallel'nye vychisleniya i zadachi upravleniya», Moskva 2-4 oktyabrya 2006. RASO’2006 [Proceedings of the third international
conference "parallel computations and control problems", Moscow, 2-4 October 2006. RASO’2006], pp. 897-908.
18. Sigal I.Kh., Babinskaya Ya.L., Posypkin M.A. Parallel'naya realizatsiya metoda vetvey i granits v zadache kommivoyazhera na baze biblioteki BNB-Solver [Parallel implementation of the method of branches and borders in the traveling salesman problem on the basis of the library BNB-Solver], Trudy ISA RAN [Proceedings of ISA RAS], 2006, Vol. 25, pp. 26-36.
19. Posypkin M.A, Sigal I.Kh. Primenenie parallel'nykh evristicheskikh algoritmov dlya uskoreniya parallel'nogo metoda vetvey i granits [Application of parallel heuristic algorithms for the parallel acceleration of the method of branches and borders], Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki [Computational mathematics and mathematical physics], 2007, Vol. 47, No. 9, pp. 1524-1537.
20. Bazylevych R., Kuz B., Kutelmakh R. Parallel Approaches for Solving Large-scale Travelling Salesman Problem, Second International Conference "Cluster Computing" CC, June 3-5, 2013, pp. 30-34.
21. Dimitrijevic V., Milosavljevic M., Markoviс M. Branch and bound algorithm for solving a generalized traveling salesman problem, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. – Mat. 7 (1996), pp. 31-35.