Global optimization for atomic cluster distance geometry problems

This chapter is devoted to a survey of global optimization methods suitable for the reconstruction of the three-dimensional conformation of atomic clusters based on the possibly noisy and imprecise knowledge of a sparse subset of pairwise distances. The problem we address is that of finding the geometry of a three-dimensional object without making use of any structural knowledge, but relying only on a subset of measured pairwise distances. The techniques we present are based on global optimization methods applied to different formulations of the problem. The methods are based on the use of standard local searches within a global optimization (GO) method which is based on local perturbation moves. Different definitions of these perturbations lead to different methods, whose performances are compared. Both sequential and population-based variants of the methods are reviewed in this chapter and some relevant numerical results are presented. From the evidence reported, it can be concluded that, when no additional information is available, such as, e.g., information about a linear order which allows for using a build-up technique, the methods proposed in this chapter represent an effective tool for difficult distance geometry problems (DGPs).