Synchronous Load Balancer for Traveling Salesman Problem

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.