When a weighted graph is an instance of the Distance Geometry Problem (DGP), certain types of vertex orders (called discretization orders) allow the use of a very efficient, precise and robust discrete search algorithm (called Branch-and-Prune). Accordingly, finding such orders is critically important in order to solve DGPs in practice. We discuss three types of … Read more
The Euclidean distance geometry problem (EDGP) includes locating sensors in a sensor network and constructing a molecular configuration using given distances in the two or three-dimensional Euclidean space. When the locations of some nodes, called anchors, are given, the problem can be dealt with many existing methods. An anchor-free problem in the three-dimensional space, however, … Read more
A Euclidean distance matrix is one in which the $(i,j)$ entry specifies the squared distance between particle $i$ and particle $j$. Given a partially-specified symmetric matrix $A$ with zero diagonal, the Euclidean distance matrix completion problem (EDMCP) is to determine the unspecified entries to make $A$ a Euclidean distance matrix. We survey three different approaches … Read more
We propose the DISCO algorithm for graph realization in $\real^d$, given sparse and noisy short-range inter-vertex distances as inputs. Our divide-and-conquer algorithm works as follows. When a group has a sufficiently small number of vertices, the basis step is to form a graph realization by solving a semidefinite program. The recursive step is to break … Read more
When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different … Read more
We recently discovered 5 new putative globally optimum configurations for Morse clusters at $\rho=8$. This report contains some algorithmic details as well as the structures determined with our method. CitationTechnical Report DSI 3-2003, Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Firenze, 2003.ArticleDownload View PDF
A standard stochastic global optimization method is applied to the challenging problem of finding the minimum energy conformation of cluster of identical atoms interacting through the Lennard-Jones potential. The method proposed is based on the use of a two-phase local search procedure which is capable of significantly enlarge the basin of attraction of the global … Read more