A Parallel BP Algorithm for the Discretizable Distance Geometry Problem

We propose a parallel version of the Branch & Prune (BP) algorithm for the Discretizable Distance Geometry Problem (DDGP), which consists in a subclass of Distance Geometry Problems (DGPs) that can be discretized. The main idea is to split a DDGP instance in as many sub instances as the number of processors involved in the computation, and to invoke the sequential version of BP on each processor. Due to the flexibility of the discretizing orderings that can be defined on the vertex sets of graphs G representing DDGP instances, the subdivision of the original instance can be performed so that all solutions generated by locally solving the several sub instances are represented in a common coordinate system. This way, the communication phase of the parallel algorithm, where the local solutions are combined in order to generate the final set of solutions, is very efficient. We present some preliminary computational experiments and we study the behavior of the algorithm in relation to the number of considered processors. We also give some directions for transforming DDGP instances in parallelizable instances, and to modify them in order to improve the efficiency of the proposed parallel algorithm.