Synchronous Load Balancer for Traveling Salesman Problem

Andrei Gorchakov

Abstract


When developing parallel methods for solving many numerical methods for solving applied problems, in particular the branch-and-bound method, the problem of load balancing arises. The choice of implementation options at the moment has been proposed quite a lot. First of all, schemes with a dedicated control process are considered, which issues tasks to the processes ”solvers”and collects from them the results of solving subtasks. The next type of load balancing is a tree-like diagram of processes corresponding to the solution tree of the problem. At the same time, for all load balancing options, the issue of scaling arises. The answer to this question can be obtained either through large-scale testing or through simulation. This paper considers a parallel implementation of one of the branch-and-bound method variants for solving the asymmetric traveling salesman problem. The method was developed in the python programming language, using the mpi4py package, which provides the functionality of the Message Passing Interface (MPI) standard for the Python programming language, which allows any Python program to use multiple processors. Load balancing is provided through synchronous (blocking) collective operations. A numerical experiment was carried out on a subset of the test set of TSPLIB problems. Based on the collected data, the main characteristics of the load balancer and its bottlenecks are identified. In addition, statistical modeling was carried out to determine the quality of the load balancer in the case of its scaling up to 107 processes.

Full Text:

PDF (Russian)

References


The traveling salesman problem: a computational study / David L Applegate, Robert E Bixby, Vasek Chvatal, William J Cook.–– Princetonuniversity press, 2006.

Gutin Gregory, Punnen Abraham P. The traveling salesman problemand its variations.–– Springer Science Business Media, 2006.––Vol. 12.

Posypkin M. S., Segal I.H. Investigation of parallel computation algorithms in knapsack-type discrete optimization problems // Journal of Computational Mathematics and Mathematical Physics .–– 2005.––Vol. 45, no. 10.–– P. 1801–1809.

Segal I.H., Ivanova A.P. Introduction to Applied Discrete Programming. Models and computational algorithms .––2007.

Bellmore Mandell, Malone John C. Pathology of traveling-salesman subtour-elimination algorithms //Operations Research.–– 1971.––Vol. 19, no. 2.–– P. 278–307.

Clapper Brian. Munkres implementation for python.– – 2019.–– URL:https://github.com/bmc/munkres(online; accessed: 2020-07-23).

Kuhn Harold W. The hungarian method for the assignment problem //Naval research logistics quarterly.–– 1955.–– Vol. 2, no. 1-2.–– P. 83– 97.

Kuhn Harold W. Variants of the hungarian method for assignmentproblems // Naval research logistics quarterly.–– 1956.–– Vol. 3,no. 4.–– P. 253–258.

Munkres James. Algorithms for the assignment and transportationproblems // Journal of the society for industrial and applied math-ematics.–– 1957.–– Vol. 5, no. 1.–– P. 32–38.

Reinelt Gerhard. Tsplib—a traveling salesman problem library //ORSA journal on computing.–– 1991.– Vol. 3, no. 4.– P. 376–384.

Parallel distributed computing using python / Lisandro D Dalcin,Rodrigo R Paz, Pablo A Kler, Alejandro Cosimo // Advances in WaterResources.–– 2011.–– Vol. 34, no. 9.–– P. 1124–1139.

Regulations of CKP ”Computer Science”.–– 2020.– – URL:http://www.frccsc.ru/ckp(online; accessed: 2020-07-23).

Gorchakov A.Y., Posypkin M.A. Comparison of options for multithreaded implementation of branch and boundary methods for multicore systems // Modern information technologies and IT education .–– 2018.––Vol. 14, no. 1.

Gorchakov A.Y., Posypkin M.A., Yamchenko Y.B. Experimental study of three variants of non-uniform coverage method implementation for multicore systems with shared memory // Interna-tional Journal of Open Information Technologies.–– 2018.–– Vol. 6,no. 11.

A Modern Introduction to Probability and Statistics: Understandingwhy and how / Frederik Michel Dekking, Cornelis Kraaikamp, Hen-drik Paul Lopuhaä, Ludolf Erwin Meester.–– Springer Science Business Media, 2005.


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2020

ISSN: 2307-8162