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 method based on local perturbation moves. Different definitions of these perturbations lead to different methods, whose relative merits are compared. Both sequential as well as 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 safely concluded that when no specific information is available, like, e.g., a linear order which allows for a build-up technique, the methods proposed in this chapter represent an effective tool for difficult distance geometry problems.