A parallel branch-and-bound algorithm for multicommodity location with balancing requirements

This article presents a parallel branch-and-bound algorithm for solving the multicommodity location problem with balancing requirements, that is based on the best known sequential method for solving the problem. The algorithm aims to exploit parallelism by dividing the search tree among processes and by performing operations on several subproblems simultaneously. The algorithm is divided into two phases: synchronous initialization and asynchronous exploration. Experimental results on a distributed network of workstations are reported and analyzed.