The Distance Geometry Problem (DGP) asks whether a simple weighted undirected graph can be realized
in a given space (generally Euclidean) so that a given set of distance constraints (associated to the
edges of the graph) is satisfied. The Discretizable DGP (DDGP) represents a subclass of instances where
the search space can be reduced to a discrete domain having the structure of a tree. In the ideal case
where all distances are precise, the tree is binary and one singleton, representing one possible position
for a vertex of the graph, is associated to every tree node. When the distance information is however not
precise, the uncertainty on the distance values implies that a three-dimensional region of the search space
needs to be assigned to some nodes of the tree.
By using a recently proposed coarse-grained representation for DDGP solutions, we extend in this work the branch-and-prune (BP) algorithm so that it can efficiently perform an exhaustive search of the search domain, even when the uncertainty on the distances is important. Instead of associating singletons to nodes, we consider a pair consisting of a box and of a most-likely position for the vertex in this box. Initial estimations of the vertex positions in every box can be subsequently refined by using local optimization.
The aim of this paper is two-fold: (i) we propose a new simple method for the computation of the three-dimensional boxes to be associated to the nodes of the search tree; (ii) we introduce the resolution parameter rho, with the aim of controling the similarity between pairs of solutions in the solution set. Some initial computational experiments show that our algorithm extension, differently from previously proposed variants of the BP algorithm, is actually able to terminate the enumeration of the solution set by providing solutions that differ from one another accordingly to the given resolution parameter.