THE MOLECULE PROBLEM - EXPLOITING STRUCTURE IN GLOBAL OPTIMIZATION

The molecule problem is that of determining the relative locations of a set of objects in Euclidean space relying only upon a sparse set of pairwise distance measurements. This NP-hard problem has applications in the determination of molecular conformation. The molecule problem c an be naturally expressed as a continuous, global optimization problem , but it also has a rich combinatorial structure. This paper investiga tes how that structure can be exploited to simplify the optimization p roblem. In particular, we present a novel divide-and-conquer algorithm in which a large global optimization problem is replaced by a sequenc e of smaller ones. Since the cost of the optimization can grow exponen tially with problem size, this approach holds the promise of a substan tial improvement in performance. Our algorithmic development relies up on some recently published results in graph theory. We describe an imp lementation of this algorithm and report some results of its performan ce on a sample molecule.