  The distance geometry problem asks to find a realization of a given simple
edge-weighted graph in a Euclidean space of given dimension K, where the edges
are realized as straight segments of lengths equal (or as close as possible) to
the edge weights. The problem is often modelled as a mathematical programming
formulation involving decision variables that determine the position of the
vertices in the given Euclidean space. Solution algorithms are generally
constructed using local or global nonlinear optimization techniques. We present
a new modelling technique for this problem where, instead of deciding vertex
positions, formulations decide the length of the segments representing the
edges in each cycle in the graph, projected in every dimension. We propose an
exact formulation and a relaxation based on a Eulerian cycle. We then compare
computational results from protein conformation instances obtained with
stochastic global optimization techniques on the new cycle-based formulation
and on the existing edge-based formulation. While edge-based formulations take
less time to reach termination, cycle-based formulations are generally better
on solution quality measures.

Optimization and Control;Computational Geometry