Claudia D'ambrosio
email: dambrosio@lix.polytechnique.fr

Khac Ky

Carlile Vu
email: vu@lix.polytechnique.fr

Leo Lavor
email: clavor@ime.unicamp.br

Nelson Liberti
email: liberti@lix.polytechnique.fr

Maculan
email: maculan@cos.ufrj.br

C D'

Ambrosio • Ky Vu

C Lavor

L Liberti

N Maculan

New Error Measures and Methods for Realizing Protein Graphs from Distance Data

Keywords: distance geometry, protein conformation, mathematical programming

come   L'archive ouverte pluridisciplinaire

Introduction

The Distance Geometry Problem (DGP) is defined formally as follows: given an integer K > 0, a simple undirected graph G = (V, E), and an edge weight function U : E → R + , establish or deny the existence of a vertex realization function x : V → R K such that:

∀{u, v} ∈ E xu -xv 2 = Uuv;
(1) realizations satisfying [START_REF] Alfakih | Solving Euclidean distance matrix completion problems via semidefinite programming[END_REF] are called valid realizations. The DGP arises in many important applications: determination of protein conformation from distance data [START_REF] Malliavin | Distance geometry in structural biology[END_REF], localization of mobile sensors in communication networks [START_REF] Ding | Sensor network localization, Euclidean distance matrix completions, and graph realization[END_REF], synchronization of clocks from phase information [START_REF] Singer | Angular synchronization by eigenvectors and semidefinite programming[END_REF], control of unmanned submarine fleets [START_REF] Bahr | Cooperative localization for autonomous underwater vehicles[END_REF], spatial logic [START_REF] Du | The logic of NEAR and FAR[END_REF], and more [START_REF] Liberti | Euclidean distance geometry and applications[END_REF]. It is NP-complete when K = 1 and NP-hard for larger values of K [START_REF] Saxe | Embeddability of weighted graphs in k-space is strongly NP-hard[END_REF]. Notationwise, we let n = |V | and m = |E|.

The aim of this paper is to find the quality-wise best and pratically fastest method for solving a DGP variant arising in finding the shape of proteins using incomplete and imprecise distance data. We achieve this through an extensive computational benchmark of many (new and existing) heuristic methods and many instances constructed from Protein Data Bank (PDB) data [START_REF] Berman | The protein data bank[END_REF]. First, however, we make a theoretical contribution related to a new solution quality measure which is specially suited to evaluate the solution quality of protein isomers (i.e. proteins which have the same chemical composition but a different shape). This is necessary to evaluating the computationally obtained solutions, since the symmetry group of protein backbones contains partial reflections [START_REF] Liberti | The discretizable molecular distance geometry problem seems easier on proteins[END_REF] (these are visible in most molecules, which may occur in nature in their left handed or right handed conformation).

The number of solutions

Let X be the set of valid realizations of G. If x ∈ X, any congruence (translation, rotation, reflection) of x yields another valid realization of G. We therefore focus on the quotient set X = X/ ∼, where x ∼ y whenever there is a congruence mapping x to y.

We have that X = ∅ if the corresponding DGP instance has no solutions; G is rigid if |X| is finite; G is globally rigid if |X| = 1; and G is flexible if |X| is uncountable. We note that |X| cannot be countably infinite. By Milnor's theorem on the Betti numbers of real algebraic varieties [START_REF] Milnor | Topology from the differentiable viewpoint[END_REF], the number of connected components of X is bounded above by 2 × 3 nK-1 . Suppose that |X| is countably infinite: then it cannot be flexible. This implies that incongruent elements of X are on distinct connected components of the manifold containing X. Milnor's theorem shows that there are only finitely many such connected components, which implies that |X| is finite. This result also follows by the cylindrical decomposition theorem of semi-algebraic sets [START_REF] Basu | Algorithms in real algebraic geometry[END_REF][START_REF] Benedetti | Real algebraic and semi-algebraic sets[END_REF].

Proteins and the Branch-and-Prune algorithm

Our motivating application is finding the shape of protein proteins in space (thus we fix K = 3) knowing interval estimations of some of the inter-atomic distances [START_REF] Cassioli | An algorithm to enumerate all possible protein conformations verifying a set of distance constraints[END_REF]. The protein backbone graph G belongs to a specific subclass of Henneberg type I graphs [START_REF] Tay | Generating isostatic frameworks[END_REF], namely there is an order < on V such that, for each v > 3, v is adjacent to v -1, v -2, v -3 [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF]. The backbone itself provides such an order on the atoms, although other orders, which may be more convenient to algorithmic efficiency, have been defined [START_REF] Lavor | Discretization orders for distance geometry problems[END_REF][START_REF] Cassioli | Discretization vertex orders for distance geometry[END_REF]. DGP instances with this property form a problem called Discretizable Molecular Distance Geometry Problem (DMDGP), which is also NP-hard [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF]. In [START_REF] Liberti | A branch-and-prune algorithm for the molecular distance geometry problem[END_REF], we proposed a fast and accurate mixed-combinatorial algorithm for solving the DMDGP, called Branch-and-Prune (BP). Unsurprisingly, the BP has exponential complexity in the worst case, but the DMDGP has many interesting properties which hold almost surely:

-G is rigid, so |X| is finite; [START_REF] Liberti | A branch-and-prune algorithm for the molecular distance geometry problem[END_REF] in particular, |X| is a power of two; [START_REF] Liberti | On the number of realizations of certain Henneberg graphs arising in protein conformation[END_REF] the BP algorithm is Fixed-Parameter Tractable (FPT) on the DMDGP [START_REF] Liberti | The discretizable molecular distance geometry problem seems easier on proteins[END_REF],

and in all the protein instances we tested, the parameter was always fixed at the same constant, yielding polytime behaviour.

By "almost surely" we mean that the set of weighted input graphs for which the above properties may not hold has Lebesgue measure zero in the set of all weighted input graphs (assuming the weights to be real numbers). The BP algorithm relies on the given distances being precise; unfortunately, however, inter-atomic distance data measured through Nuclear Magnetic Resonance (NMR) are subject to experimental errors, modelled as real intervals [L, U ] assigned to all edges {u, v} whenever v -u ≥ 3 in the vertex order. To overcome this difficulty, two research directions have been pursued: (i) the discretization of the uncertainty intervals [START_REF] Lavor | The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF]; (ii) the analytical description, using Clifford algebra, of the locus of vertex v when the edge {v, v -3} is weighted by an interval [START_REF] Lavor | Clifford algebra and the discretizable molecular distance geometry problem[END_REF]. The formulation study in this paper moves a first step towards a third direction: the integration of purely continuous techniques within mixed-combinatorial algorithms such as BP. To this end, in this paper we pursue a computational study of some these techniques.

The interval DGP

This brings us to the interval Distance Geometry Problem (i DGP), which is a variant of the DGP defined as follows: the edge function is an interval function [L, U ] : E → IR + , where L, U are two nonnegative functions from E → R + such that Luv ≤ Uuv for each {u, v} ∈ E, IR + is the set of nonnegative real intervals, and Eq. ( 1) is replaced by:

∀{u, v} ∈ E Luv ≤ xu -xv 2 ≤ Uuv. (2)
Note that Eq. ( 2) is often written as:

∀{u, v} ∈ E L 2 uv ≤ xu -xv 2 2 ≤ U 2 uv . (3)
As explained later, Eq. ( 3) minimizes the chances that numerical solvers, which rely on the floating-point representation of real numbers, might stumble upon a negative representation of zero, thereby raising a "not a number" (NaN) error upon calculating the square root. Note that the i DGP contains (and hence generalizes) the DGP, since the latter corresponds to the case L = U .

Aim of this paper

Most solution techniques for solving i DGP instances require a continuous search in Euclidean space, even if the given graph is rigid. The most direct approach is to formulate the i DGP as a Mathematical Program (MP), which can then be solved by a MP solver. The aim of this paper is to determine the best solver+formulation combination for the i DGP. To this end, we need to know: (a) how to evaluate the quality of the solutions computed by the solvers; (b) which formulations to employ; (c) which solvers to employ. We therefore introduce new and existing error measures, formulations and solvers, before proceeding to evaluate them all computationally. Since we want our algorithms to be fast and scale well, we focus on heuristic approaches. This means that we forsake a proof of exactness, so evaluating these algorithms require test sets with given (trusted) solutions. Such test sets can be put together using the PDB.

Solution quality evaluation

The simplest measures used for evaluation DGP solution quality are based on computing the average or maximum relative error of the realization with respect to the given distance value on the edges. The drawback of these simple edgebased measures is that even a small error might correspond (in sufficiently large proteins) to a wrong protein shape. Even worse, plotting the DGP solution versus the trusted solution usually yields nothing to the human eye, since the alignment is likely to be completely off.

A more meaningful measure is provided by Procrustes analysis [START_REF] Goodall | Procrustes methods in the statistical analysis of shape[END_REF], also called coordinate root mean square deviation (cRMSD) [START_REF] Maiorov | Significance of root-mean-square deviation in comparing three-dimensional structures of globular proteins[END_REF]. Informally, this is the error derived by the best alignment, via translations and rotations, of a DGP solution to the trusted solution. It provides a visual tool for a human to evaluate the error, so even when the error is non-zero the visualization helps determine whether the error is due to floating point issues or structural differences.

Unfortunately, for protein backbones there is an added difficulty: their symmetry group includes at least one partial reflection (starting from the fourth atom along the backbone), and may include many more [START_REF] Liberti | On the number of realizations of certain Henneberg graphs arising in protein conformation[END_REF][START_REF] Liberti | The discretizable molecular distance geometry problem seems easier on proteins[END_REF][START_REF] Liberti | Counting the number of solutions of k DMDGP instances[END_REF]: in general, the partial reflection group structure is a cartesian product of cyclic groups of order two, yielding an exponential number of elements. All of these symmetric solutions are isomers. They are equivalent from the point of view of the simple, edge-based error measures, but they may have very different cRMSD values with respect to the trusted solution. Again, visualizing a trusted solution and a DGP solution from a heuristic method with a low cRMSD might yield structures which look nothing like each other.

The first contribution of this paper is the definition of a modified error measure that extends the cRMSD in that it aligns two structures in the best possible way using translations, rotations and partial reflections, and which allows us to properly evaluate the protein backbone solutions proposed by DGP heuristics. Our new measure could be described as a "cRMSD modulo isomers".

Innovations and outcomes

To sum up, the innovations introduced in this paper are: (i) the new cRMSD modulo isomers; (ii) some new MP formulations for the iDGP; (iii) the concept of "pointwise formulation" to be used in alternating-type algorithms; (iv) an adaptation of the Multiplicative Weights Update (MWU) algorithm to the iDGP. We conclude that the MWU algorithm with its pointwise formulation is the best combination, and that the new "square factoring" MP formulation, used within either a pure MultiStart (MS) or a Variable Neighbourhood Search (VNS) heuristic, is second best.

Structure of the paper

The rest of the paper is organized as follows. In Sect. 2, we define error measures to meaningfully compare protein backbones found algorithmically with those stored in PDB files [START_REF] Berman | The protein data bank[END_REF], and introduce a new cRMSD type measure modulo certain partial reflection isomers. In Sect. 3, we list several formulations, relaxations and variants for the i DGP, some of which are new. In Sect. 4, we propose a new algorithm for solving the i DGP: namely, an adaptation of the Multiplicative Weights Update method [START_REF] Arora | The multiplicative weights update method: a metaalgorithm and applications[END_REF]. In Sect. 5, we discuss comparative computational results, which show that, on average, our newly proposed algorithm provides the best quality solutions.

Error measures for realizations of protein graphs

Since we aim at ascertaining which formulation(s) can provide the best and/or fastest bound, we need a method to benchmark quality and speed with respect to any solution algorithm. We benchmark speed by simply measuring CPU time.

Benchmarking solution quality is more complicated. In the Turing Machine (TM) model, decision problems are in NP whenever feasible instances can be certified feasible in polynomial time. Although the DGP and i DGP are NP-hard decision problems, they are not known to be in NP: feasible instances of the DGP and i DGP can in general yield realizations with irrational components, for which polynomially-sized representations are not generally available (some simple ideas have been tried in [START_REF] Beeker | Is the distance geometry problem in NP?[END_REF] but failed to prove membership of the DGP to NP). The methods employed in this paper replace irrational numbers by floating point numbers, and, as such, do not provide a valid certificate. On the other hand, this is the situation with all real number computations that need to be carry out efficiently over medium to large-scale problems. Instead, we compute feasibility errors for the floating point solutions we obtain.

The edge error

Given a realization x * : V → R K , we can measure the error of x * with respect to a given i DGP instance by assigning an 2 -norm error to each edge {u, v} of the graph G = (V, E), given by [START_REF] Liberti | Molecular distance geometry methods: from continuous to discrete[END_REF]:

αuv(x * ) = max 0, Luv -x * u -x * v 2 + max 0, x * u -x * v 2 -Uuv . (4)
We remark that the corresponding error for non-interval DGP instances is:

βuv(x * ) = x * u -x * v 2 -Uuv .
Accordingly, we define the edge error as follows:

ηuv(x * ) = αuv(x * ) if the instance is i DGP βuv(x * ) if the instance is DGP.
We can now define the average error associated to the instance graph G and a realization x * as:

Φ(x * , G) = 1 |E| {u,v}∈E ηuv(x * ), (5)
and the maximum error as:

Ψ (x * , G) = max {u,v}∈E ηuv(x * ). ( 6
)
The above are absolute edge error measures. Relative error measures also exist, where each term Luv -xu -xv 2 is replaced by Luv-xu-xv 2 |Luv| (and similary for xu -xv 2 -Uuv. Whether one or the other is used depends on the application at hand, and how poorly scaled the input data L, U are. In the case of proteins, bounds are generall well scaled, as they are often between 1 and 6 Å; so absolute error measures are more appropriate.

The coordinate root mean square deviation

The edge errors go a long way in determining when a realization x * is not valid. In many applications, however, we know a priori that a problem instance should feasible. Take e.g. the reconstruction of protein conformations from inter-atomic distances: the protein certainly exists (this is also the case when localizing sensors in wireless networks: the network is being measured, so it exists). Furthermore, we might have a given (precise or approximate) realization x. In this setting, we want to evaluate the error with respect to the given realization x.

An obvious way to adapt the edge error to this situation is to compute the average, over edges in E, of an absolute 2 -norm distance difference:

∆(x * , x) = 1 |E| {u,v}∈E x * u -x * v 2 -xu -xv 2 . (7)
Unfortunately this approach is wrong, since different congruent realizations yield different error values, making the comparison impossible.

To this end, the cRMSD is often used instead: i.e., translate both x * and x so that their centroids γ(x * ) = γ(x) = 0, where the centroid is the vector γ(x) ∈ R K defined as:

γ(x) = v≤K xv, (8)
and then find the congruence ρ (consisting of a rotation composed with at most one reflection) such that x * -ρ(x) is minimum. Note that the norm • on R Kn is induced by the 2 -norm in R K :

x * -x = v∈V x * v -xv 2 .
(9)

The cRMSD between x * and x is defined as minρ x * -ρ(x) .

Distance error modulo isometries

Although the cRMSD is widely used in computational geometry, it still falls short in one of the properties of molecules, namely isomers, which are molecules having the same chemical formula but different 3D structure.

If we consider protein backbones only, their graphs G = (V, E) possess a further structural property. They have an order < on V such that:

1. the first K vertices in the order form a clique in G (clique property); 2. each vertex v > K is adjacent to v -1, . . . , v -K (contiguous trilateration order property).

Although protein backbones have K = 3, we develop the theory for general K. DGP instances having these properties are also collectively known as K DMDGP, which are a subclass of Henneberg type I graphs [START_REF] Henneberg | Die Graphische Statik der starren Systeme[END_REF]. Contiguous trilateration orders are also known as cTOP or K DMDGP orders [START_REF] Cassioli | Discretization vertex orders for distance geometry[END_REF]. The edges induced by these properties in a K DMDGP graph are called discretization edges, and the edges which are not discretization edges are called pruning edges.

Many mathematical aspects of the K DMDGP have been investigated in the past (see [START_REF] Liberti | On the number of realizations of certain Henneberg graphs arising in protein conformation[END_REF][START_REF] Liberti | The discretizable molecular distance geometry problem seems easier on proteins[END_REF][START_REF] Liberti | Counting the number of solutions of k DMDGP instances[END_REF]). The problem itself is NP-hard. The automorphism group of X generally contains a subgroup G P consisting of partial reflections gv, called the pruning group, such that the action of gv over a realization x ∈ X is:

gv(x) = (x 1 , . . . , x v-1 , R v x (xv), . . . , R v x (xn)), (10)
where R v x is the reflection with respect to the affine subspace spanned by x v-1 , . . ., x v-K , and where v ranges over a vertex set

Z = V ({1, . . . , K} ∪ {u,w}∈E u+K<w {u + K + 1, . . . , w}),
or, in other words, v must not be "covered" by any pruning edge.

Example 1 Consider the DGP instance with V = {1, 2, 3, 4},

E = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}
consisting of two triangles on {1, 2, 3} and {2, 3, 4}, and K = 2. There is a partial reflection ρ 1 fixing 1, 2 and reflecting 3, 4 across the line through 1, 2, and another partial reflection ρ 2 fixing 1, 2, 3 and reflecting 4 across the line through 1, 2, 3. The range of the pruning edge {1, 4} is {1 + K + 1, . . . , 4} = {4}. Therefore, if we add {1, 4} to E, Z = {3}, which means that the pruning group of this instance has the single generator ρ 1 .

The protein backbone isomers of a valid realization x are given by the orbit G P x = {gv(x) | v ∈ Z}. It turns out that all backbone isomers in G P x are valid realizations of the given DGP instance G. So we might obtain a realization x * which is a valid isomer (and hence has zero edge errors), but has a large cRMSD with the given (different) isomer x.

A serious issue arises when considering i DGP instances, however: if the cRMSD between x * and x is positive, is it due to the "slack" induced by the interval edge weights, or is it due to the fact that x * and x are different isomers of essentially the same backbone (a similar issue was described in [START_REF] Maiorov | Significance of root-mean-square deviation in comparing three-dimensional structures of globular proteins[END_REF])? This motivates us to define the following problem:

Distance Error Modulo Isometries (DEMI). Given integers n, K with n ≥ K, two n-point realizations x, y ∈ R Kn such that the centroids γ(x) = γ(y) = 0, and a description of a pruning group G P , find the rotation ρ and a partial reflection composition g ∈ G P such that x -gρ(y) is minimum.

Note that groups can be described by listing their elements, or by a set of generators (and possibly relations) which, when multiplied together up to closure, are guaranteed to generate the whole group. The latter description is usually much shorter than the former.

We let ∂(x, y) be the minimum value of x -gρ(y) which solves the DEMI. We note that ∂ is not a semimetric (hence not even a metric), since ∂(x, y) can be zero even though x = y (just take y as a partial reflection of x).

Complexity of DEMI

The computational complexity class of DEMI depends on the description of the pruning group. If it is given explicitly, by listing all the partial reflection compositions in G P , then the trivial Algorithm 1 solves the problem in polynomial time for fixed K. For a realization x ∈ R Kn and an integer h ≤ n, let x[h] be the partial realization

(x i | 1 ≤ i ≤ h).
Step 1 takes a polynomial amount of time for fixed Algorithm 1 SolveDEMI(x, y, G P )

1: Find a congruence ρ minimizing x[K] -y[K] 2: Let ∂(x, y) = min{ x -gρ(y) | g ∈ G P }
K (an O(n K-2 log n) algorithm was described in [START_REF] Alt | Congruence, similarity and symmetries of geometric objects[END_REF]), but more efficient methods exist for K = 3, see [START_REF] Atkinson | An optimal algorithm for geometrical congruence[END_REF][START_REF] Coutsias | Using quaternions to calculate rmsd[END_REF]. Step 2 depends linearly on the order of the pruning group, which was shown in [START_REF] Liberti | Counting the number of solutions of k DMDGP instances[END_REF] to be 2 |Z| . Since Z is usually small in practice (see Sect. 2.3.2) and on average (see Sect. 2.3.3), assuming the input to DEMI to be the explicit list of all partial reflection compositions is not out of place.

We have not been able to prove that DEMI can be solved in polynomial time (for fixed K) if its input is x, n, and the compact group generators description Z, nor that DEMI is NP-hard under the same conditions. We leave this as an open question.

Empirical observations on the size of Z

In this section we exhibit empirical evidence to the effect that |Z| is rarely large. First, we note that |Z| ≥ 1: this follows by the definition of Z = {v > K | {u, w} ∈ E (u + K < v ≤ w)}, since v = K + 1 is obviously always in Z (this can also be shown by other means [29, Sect. 2.1]).

Figures 12show the mean and standard deviations of |Z| relative to samples of 500 randomly generated K DMDGP instances for each value of K ∈ {2, 3} and various values of the edge sparsity s. The generation procedure is as follows: given n = |V | and K, we initially generate a K DMDGP instance with all the necessary discretization edges in its edge set E (there are K(K -1)/2 + (n -K)K of them), but no pruning edges. Then we loop over all {i, j} which are not discretization edges, and with given probability s we insert a pruning edge in E. So s is in fact the density of the pruning edges.

The exact dependency of |Z| on the number of pruning edges is given in [START_REF] Liberti | The discretizable molecular distance geometry problem seems easier on proteins[END_REF], and it is used to show that the BP algorithm is FPT. It should be clear by definition that the denser the graph, the smaller Z must be. Figures 12show (empirically) that |Z| tends to 1 very fast and very reliably as n and s increase, with n, s as small as, respectively, 20 and 0.3. Large graphs with |Z| > 1 are very rare.

It is interesting to note that the standard deviation of |Z| as a function of the sparsity s has a maximum in [0, 0.05] (see Fig. 2). This phenomenon is analyzed below in more detail.

Expectation and variance of |Z|

As explained in Sect. 2.3, K DMDGP instances consist of a backbone subgraph (a minimal graph satisfying the clique and contiguous trilateration order properties) and some pruning edges. Accordingly, random K DMDGP graphs G = (V, E) are generated as follows:

a backbone which only depends on K, n and determines the order on V ; -for each pair {u, w} which is not a discretization edge, we independently add {u, w} as a pruning edge in E with probability s ∈ [0, 1]. Now consider the subset Z ⊆ V , defined as in Sect. 2.3 as

Z = {v > K | {u, w} ∈ E (u + K < v ≤ w)}.
We consider |Z| as a random variable depending on the edge probability s (also known as the sparsity of the K DMDGP graph G), and compute its expected value. In the following, P(•) is the probability of an event, E(•) is the expectation of a random variable and Var(•) is its variance.

Proposition 1 E(|Z|) ≤ 1 + (n -K -1)(1 -s) n-K-1 . Proof For all v ∈ {K + 1, . . . , n} define Xv = 0 if v / ∈ Z and 1 if v ∈ Z. Then |Z| = n v=K+1
Xv, which implies: Now, for any v ∈ {K + 1, . . . , n} there are v -K -1 choices of u with u + K < v, and there are n-v +1 choices of w with v ≤ w. Therefore, there are (v -K -1)(n-v +1) possible choices of the pruning edge {u, w} such that u + K < v ≤ w. Moreover, v ∈ Z if all these pairs are not added to the graph. Thus, and hence:

E(|Z|) = n v=K+1 E(Xv) = n v=K+1 P(v ∈ Z).
P(v ∈ Z) = (1 -s) (v-K-1)(n-v+1) , n/K 2 3
E(|Z|) = n v=K+1 (1 -s) (v-K-1)(n-v+1) .
Finally, we remark that (a) the first term of the sum is 1, and (b) (1 -s) < 1, so we can replace all the terms of the sum by the second largest one, and obtain:

E(|Z|) ≤ 1 + (n -K -1)(1 -s) n-K-1 , (11)
as claimed.

2

The RHS of Eq. ( 11) converges to 1 as s → 1 with n, K fixed, and as n → ∞ with s, K fixed, which is consistent with the empirical results of Sect. 2.3.2. We are therefore justified in making the qualitative statements that, for random DMGDP, |Z| ≈ 1.

We now discuss the variance. Since Var(|Z|) = Var( n v=K+1 Xv), then by a property of sum of correlated variables [START_REF] Wikipedia | Sum of correlated variables[END_REF], we have:

Var(|Z|) = n v=K+1 Var(Xv) + 2 k+1≤v1<v2≤n Cov(Xv 1 , Xv 2 ) = n v=K+2 Var(Xv) + 2 k+2≤v1<v2≤n Cov(Xv 1 , Xv 2 ) (this follows from E(X K+1 ) = 1 and E(X K+1 Xv) = E(Xv) for all v) = n v=K+2 E(Xv) + k+2≤v1<v2≤n E(Xv 1 Xv 2 )+ - n v=K+2 [E(Xv)] 2 -2 k+2≤v1<v2≤n E(Xv 1 )E(Xv 2 ). By definition of Z, two vertices v 1 and v 2 are in Z if all pairs {u, w} such that either u + K < v 1 ≤ w or u + K < v 2 ≤ w are not edges of G. Assume v 1 < v 2 , then there are: (v 1 -K -1)(n -v 1 + 1) + (v 2 -K -1)(n -v 2 + 1) -(v 1 -K -1)(n -v 2 + 1) = (v 1 -K -1)(n -v 1 + 1) + (v 2 -v 1 )(n -v 2 + 1)
such edges (by counting all pairs of each type and subtracting the number of doubly counted ones). So, the probability that

v 1 , v 2 ∈ Z is (1 -s) (v1-K-1)(n-v1+1)+(v2-v1)(n-v2+1) .

This implies

Var(|Z|) = n v=K+2 (1 -s) (v-K-1)(n-v+1) - n v=K+2 (1 -s) 2(v-K-1)(n-v+1) + + 2 K+2≤v1<v2≤n (1 -s) (v1-K-1)(n-v1+1)+(v2-v1)(n-v2+1) - -2 K+2≤v1<v2≤n (1 -s) (v1-K-1)(n-v1+1)+(v2-K-1)(n-v2+1) .
To simplify the analysis of Var(|Z|), we provide an upper bound.

Lemma 1 For all s ∈ (0, 1) and k ≥ 1, we have

k-1 i=1 (1 -s) i(k-i) < 2(1-s) k-1 s . Proof For each 1 ≤ i < k
2 we have the estimate

(i + 1)(k -i -1) = ik + k -i 2 -2i -1 = i(k -i) + k -2i -1 ≥ i(k -i) + 1. ( 12
)
Therefore,

k-1 i=1 (1 -s) i(k-i) ≤ 2 k 2 i=1 (1 -s) i(k-i) ≤ 2((1 -s) k-1 + (1 -s) k + (1 -s) k+1 + . . . + (1 -s) k-2+ k 2 ) < 2(1 -s) k-1 ∞ i=0 (1 -s) i = 2(1 -s) k-1
s .

The second inequality follows because of estimate [START_REF] Biswas | Semidefinite programming approaches to distance geometry problems[END_REF].

2

We can now improve the estimate for the variance (where n, K only appear in the exponent):

0 < Var(|Z|) < n v2=K+2 (1 -s) (v2-K-1)(n-v2+1) + 2 K+2≤v1<v2≤n (1 -s) (v1-K-1)(n-v1+1)+(v2-v1)(n-v2+1) < n-K-1 i=1 (1 -s) i(n-K-i) + 2 K+2≤v1≤n (1 -s) (v1-K-1)(n-v1+1) n-v1 i=1 (1 -s) i(n-v1-i+1) < 2 s (1 -s) (n-K-1) + 4 s K+2≤v1≤n (1 -s) (v1-K-1)(n-v1+1) (1 -s) n-v1 (Lemma 1) = 2 s (1 -s) (n-K-1) + 4 s(1 -s) n-K i=2 (1 -s) i(n-K-i+1) < 2 s (1 -s) (n-K-1) + 4 s(1 -s) ( 2 s -1)(1 -s) n-K (Lemma 1) = 8 s 2 - 2 s (1 -s) n-K-1 .
For example, with s = 0.2, n = 35, K = 2, the estimate yields 8

s 2 -2 s (1 - s) n-K-1 = 0.15. With s = 0.3, n = 25, K = 2, we get 8 s 2 -2 s x(1 -s) n-K-1 = 0.03.
Fig. 2 shows that the standard deviation (and hence the variance) of |Z| has a maximum when s is close to zero. Fixing n and K, consider Var(|Z|) as a function f (t) of 1 -s, let τ (k) = kt k , and rewrite Var(|Z|) as:

Var(|Z|) = f (t) = n v=K+2 t (v-K-1)(n-v+1) - n v=K+2 t 2(v-K-1)(n-v+1) + + 2 K+2≤v1<v2≤n t (v1-K-1)(n-v1+1)+(v2-v1)(n-v2+1) - -2 K+2≤v1<v2≤n t (v1-K-1)(n-v1+1)+(v2-K-1)(n-v2+1) .
Taking the derivative of f (t), we have:

f (t) = t -1   n v=K+2 τ ((v -K -1)(n -v + 1)) - n v=K+2 τ (2(v -K -1)(n -v + 1)) + + 2 K+2≤v1<v2≤n τ (v 1 -K -1)(n -v 1 + 1) + (v 2 -v 1 )(n -v 2 + 1) - -2 K+2≤v1<v2≤n τ ((v 1 -K -1)(n -v 1 + 1) + (v 2 -K -1)(n -v 2 + 1))   .
Consider the derivative of τ with respect to k, τ (k) = (kt k ) = t k (1 + k ln(t)), and take for example k ≥ 20 and t ≤ 0.95. We have (1

+ k ln(t)) ≤ 1 + 20 ln(0.95) = -0.026 < 0. Therefore, when t < 0.95, τ (k) is a decreasing function on the set {k | k ≥ 20}. It means that, whenever n -K -1 ≥ 20, τ ((v -K -1)(n -v + 1)) ≥ τ (2(v -K -1)(n -v + 1)) for each v ∈ {K + 2, . . . , n}, and τ ((v 1 -K -1)(n -v 1 + 1) + (v 2 -v 1 )(n -v 2 + 1)) ≥ τ ((v 1 -K -1)(n -v 1 + 1) + (v 2 -K -1)(n -v 2 + 1)) for each v 1 < v 2 ∈ {K + 2, . . . , n},
since all values under τ are at least 20. We therefore have that f (t) ≥ 0 for all t < 0.95, i.e., whenever s ∈ [0.05, 1], Var(|Z|) decreases as s increases. In other words, the maximum of Var(|Z|) can only be attained on [0, 0.05]. We can generalize this example to the following result.

Lemma 2 For fixed n, K, the maximum of Var(|Z|) can only be attained at s ∈ [0,

1 n-K-1 ]. Proof We have τ (k) < 0 ⇔ 1 + k ln(t) < 0 ⇔ ln( 1 t ) > 1 k ⇔ 1 t > e 1/k ⇔ t < e -1/k ⇔ s > 1 -e -1/k . Since e -1/k = 1 - 1 k + 1 2!k 2 - 1 3!k 3 + . . . > 1 - 1 k , we have 1-e -1/k < 1 k . Therefore, if s > 1 k we have τ (k) < 0. So, when s > 1 n-K-1 , we have τ (k) < 0 for all k ≥ n -K -1
. Now the same argument as in the example above shows that Var(|Z|) decreases on the set [

1 n-K-1 , ∞).

Computing DEMI measures in practice

We believe we made a convincing argument that we can safely use Alg. 1 to solve DEMI instances. There is, however, a glitch: none of the PDB instances we consider actually comes with a pre-defined cTOP order. For some of them, the protein backbone is a cTOP order. For others this is not the case. The state of the art in automatically finding cTOP orders in graphs is severely limited [START_REF] Cassioli | Discretization vertex orders for distance geometry[END_REF], and certainly does not scale to hundreds of vertices easily. Thus the DEMI measure ∂(x, y) of a realization x with respect to a given realization y will not be computed for all instances we test in Sect. 5, but only for some (see Table 10).

New and existing i DGP formulations

All formulations we consider are box-constrained to bounds x ∈ [M L , M U ] Kn , which have to be large enough to accommodate a worst-case realization with the given distances. One could take for example M L = -1 2 {u,v}∈E Uuv and M U = -M L , and then tighten these bounds using some pre-processing techniques [START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF]. We do not write these bounds explicitly in the formulations below. Notationwise,

M = [M L , M U ] m and M + = M ∩ [0, +∞].
Most formulations come with variants. A common variant, which we refer to as the square root variant, is the following: replace xu -xv 2 2 by xu -xv 2 and squared distance bounds by distance bounds. In such variants, because of floating point issues, √ α is implemented as

√ α + δ, where δ is a constant in O(10 -10 ).
In all of our formulations, aside from the semidefinite programming (SDP) ones, we fix the centroid at the origin, which means that we find solutions modulo translations. This seems to improve the overall reliability and convergence speed of the heuristic solution algorithms we use. It is interesting that this ceases to be the case if we also impose no rotation by fixing the first K vertices, in which case the algorithms find much worse local optima.

Validation

With each formulation, we present performances and results on a single PDB instance called tiny, which describes a graph G tiny = (V, E) with |V | = 37, |E| = 335 and K = 3. Fig. 3 shows a heat map of the partial Euclidean Distance Matrix (pEDM) and the correct realization (found in the PDB file) in R K using two types of plots.

These validation experiments consist in solving the tiny instance using three different Global Optimization (GO) methods. The first method is a deterministic GO solver based on spatial Branch-and-Bound (sBB) [START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF], which we run for at most 900s. The second method is a stochastic matheuristic called Variable Neighbourhood Search (VNS), described in [START_REF] Liberti | Variable neighbourhood search for the global optimization of constrained NLPs[END_REF] with some adaptations from [START_REF] Liberti | A recipe for finding good solutions to MINLPs[END_REF]. The third method is a straightforward MultiStart (MS) algorithm, which is possibly the simplest stochastic metaheuristic, and consists of deploying a certain number of local descents from randomly sampled initial points. Both VNS and MS were allowed to run for at most 20s of user CPU time (but terminated whenever they found an optimum with average error less than 10 -6 ). The results report the average edge error Φ (see Eq. ( 5)), the maximum edge error Ψ (see Eq. ( 6)), the DEMI measure ∂, and the CPU time in seconds. All statistics referring to stochastic algorithms are averaged over 10 runs.

These validation experiments were conducted on a single core of a two-core Intel i7 CPU running at 2.0GHz with 8GB RAM under the Darwin Kernel v. 13.3.0. Our sBB solver of choice is Couenne [START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF] in its default setting. We used AMPL [START_REF] Fourer | The AMPL Book[END_REF] to implement the VNS and MS algorithm, and Ipopt [START_REF] Coin-Or | Introduction to IPOPT: A tutorial for downloading, installing, and using IPOPT[END_REF][START_REF] Wächter | On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming[END_REF] as a local solver. The SDP formulations were modelled using YalMIP [START_REF] Löfberg | YALMIP: A toolbox for modeling and optimization in MATLAB[END_REF] running under MATLAB [START_REF]MATLAB R2014a[END_REF] and solved using Mosek [START_REF] Aps | The mosek manual[END_REF].

The point of these preliminary experiments is to visually show how the DEMI error measure ∂ impacts structural differences versus floating point errors. Each 3D plot contains two realizations (seen from the angle which best emphasizes their differences): the trusted solution found in the PDB, and the output of the corresponding algorithm. Floating point errors can be remarked when two realizations are almost aligned but not quite superimposed. Structural errors are evident when no alignment is visible.

Exact formulations

These formulations will yield a valid realization at every global optimum.

Penalty minimization

This formulation minimizes the sum of non-negative penalties suv deriving from the fact that xu -xv 2 is smaller than Luv or larger than Uuv:

min s∈M + ,x {u,v}∈E suv ∀{u, v} ∈ E L 2 uv -xu -xv 2 2 ≤ suv ∀{u, v} ∈ E xu -xv 2 2 -U 2 uv ≤ suv ∀k ≤ K v∈V x vk = 0.            (13)
Variants: (i) replace with max; (ii) use different variables s L , s U to represent penalties w.r.t. L, U ; (iii) replace the objective by any positive linear form in the penalty variables.

This formulation and its variants have the property that an optimum is global if and only if the objective function value is identically zero. An unconstrained and weighted version of this formulation appeared in [START_REF] Moré | Distance geometry optimization for protein structures[END_REF]. The performance of the penalty minimization formulation and its variants on the tiny instance is shown in Table 1.

Square factoring

This formulation has been adapted to the interval case from [START_REF] Ambrosio | Computational experience on distance geometry problems 2[END_REF]. It exploits the

identity xu -xv 2 2 = (xu -xv)(xu -xv): min x,σ∈M K ,τ ∈M K {u,v}∈E k≤K (σ uvk -τ uvk ) 2 ∀{u, v} ∈ E, k ≤ K x uk -x vk = σ uvk ∀{u, v} ∈ E k≤K σ uvk τ uvk ≥ L 2 uv ∀{u, v} ∈ E k≤K σ uvk τ uvk ≤ U 2 uv ∀k ≤ K v∈V x vk = 0.                      (14)
We propose no variants for this formulation. The performance of the square factoring formulation on the tiny instance is shown in Table 2.

Relaxations

These are formulations which relax some feasibility constraints. The obtained solution may or may not be a valid (feasible) solution to the given instance. One should always therefore verify that the solution satisfies [START_REF] Alt | Congruence, similarity and symmetries of geometric objects[END_REF]. On the other hand, if a relaxation is infeasible, then so must be the original i DGP instance. Table 1 Performance of penalty minimization on tiny. For each solver and formulation (variant), we report the edge errors Φ, Ψ , the CPU time, a 3D plot of the solution x tiny given in the PDB file versus the solution x DEMI found by solving the DEMI instance with x = x tiny and y given by the solution of the solver, and the corresponding DEMI measure ∂(x, y) = min g,ρ

x -gρ(y) . x -gρ(y) .

Convexity and concavity

This formulation, adapted to the interval case from [START_REF] Ambrosio | Computational experience on distance geometry problems 2[END_REF], exploits the convexity and concavity of the equations in Eq. (3) separately:

max x {u,v}∈E xu -xv 2 2 ∀{u, v} ∈ E xu -xv 2 2 ≤ U 2 uv ∀k ≤ K v∈V x vk = 0.        (15)
Variants: replace the objective with a positively weighted version thereof. Eq. ( 15) is an exact reformulation (in the sense of [START_REF] Liberti | Reformulations in mathematical programming: Definitions and systematics[END_REF]) of min x {u,v}∈E

( xu -xv 2 -U 2 uv ) 2 , ( 16
)
which is possibly the best known Mathematical Programming (MP) formulation of the (non-interval) DGP so far. That Eq. ( 16) and Eq. ( 15) have the same solutions can be intuitively visualized the edges {u, v} of the underlying graph G as a set of interconnected cables, each of length Uuv: the objective of Eq. ( 15) "pulls" the adjacent vertices u, v apart as far as possible. As a result, all cables can be straightened if and only if the DGP has a valid solution. A formal proof of this fact is given elsewhere [START_REF] Liberti | A multiplicative weights update algorithm for MINLP[END_REF].

If the given instance is an i DGP one, however, Eq. ( 15) is a relaxation of the lower bounding constraints: by attempting to maximize the distance between adjacent points, one hopes that xu -xv 2 ≥ Luv will hold, but this need not necessarily be the case. The performance of the convexity and concavity formulation and its variants on the tiny instance is shown in Table 3.

Semidefinite programming relaxation

This is a natural SDP relaxation, similar to many which already appeared in the literature, where xu -xv 2 2 is linearized to Xuu + Xvv -2Xuv:

max X 0 {u,v}∈E (Xuu + Xvv -2Xuv) ∀{u, v} ∈ E Xuu + Xvv -2Xuv ≥ L 2 uv ∀{u, v} ∈ E Xuu + Xvv -2Xuv ≤ U 2 uv ,      (17)
where X 0 means that X is required to be positive semidefinite. Several SDP formulations for the DGP have been proposed in the literature over the years, see e.g. [START_REF] Yajima | Positive semidefinite relaxations for distance geometry problems[END_REF][START_REF] Alfakih | Solving Euclidean distance matrix completion problems via semidefinite programming[END_REF][START_REF] Biswas | Semidefinite programming based algorithms for sensor network localization[END_REF][START_REF] Biswas | Semidefinite programming approaches for sensor network localization with noisy distance measurements[END_REF]. Our formulation, which addresses the i DGP, is directly inspired by those in [START_REF] Biswas | Semidefinite programming approaches to distance geometry problems[END_REF], since it employs a linearization of the constraints in Eq. ( 3). As objective function, we employ a linearization of {u,v}∈E xu -xv 2 , which is unusual. We observed empirically that this yields a good performance on datasets arising from protein conformation.

Variants: replace the objective with min Tr(X) as a proxy to rank minimization [START_REF] Candès | PhaseLift: Exact and stable signal recovery from magniture measurements via convex programming[END_REF]. The performance of the SDP relaxation and its variant on the tiny instance is shown in Table 4 Table 3 Performance of convexity and concavity on tiny. For each solver and formulation (variant), we report the edge errors Φ, Ψ , the CPU time, a 3D plot of the solution x tiny given in the PDB file versus the solution x DEMI found by solving the DEMI instance with x = x tiny and y given by the solution of the solver, and the corresponding DEMI measure ∂(x, y) = min g,ρ

x -gρ(y) . Table 4 Performance of semidefinite programming on tiny. For each formulation (variant), we report the edge errors Φ, Ψ , the CPU time, a 3D plot of the solution x tiny given in the PDB file versus the solution x DEMI found by solving the DEMI instance with x = x tiny and y given by the solution of the solver, and the corresponding DEMI measure ∂(x, y) = min g,ρ

Original

x -gρ(y) .

Yajima's SDP relaxation

This formulation was proposed in [START_REF] Yajima | Positive semidefinite relaxations for distance geometry problems[END_REF]. The term 2 {u,v}∈E Xuv added to the objective function is equal to Tr(1X) (where 1 is the all-one matrix) and has a regularization purpose, ensuring that Tr(1X) = 0 and hence that rk(X) ≤ n -1.

min s∈M + ,X 0 {u,v}∈E (suv -(Xuu + Xvv -2Xuv) + L 2 uv ) + 2 {u,v}∈E Xuv ∀{u, v} ∈ E (Xuu + Xvv -2Xuv) -L 2 uv ≤ suv ∀{u, v} ∈ E 2(Xuu + Xvv -2Xuv) -L 2 uv -U 2 uv ≤ suv      (18)
We propose no variants for this formulation. The performance of Yajima's SDP relaxation on the tiny instance is shown in Table 5.

A pointwise reformulation

Pointwise reformulations are only exact for a specific set of values assigned to certain parameters. Typically, replacing variables or entire terms by parameters makes it possible to obtain formulations for which there exist very efficient solution methods. This reformulation will be used in a stochastic search setting (see Sect. 4 below) where the global search phase occurs over the parameter values.

We replace the term (x uk -x vk ) 2 = (x uk -x vk )(x uk -x vk ) by a linear term θ uvk (x uk -x vk ) whenever it occurs in Eq. ( 3) and ( 15) in a nonconvex way:

max x {u,v}∈E k≤K θ uvk (x uk -x vk ) ∀{u, v} ∈ E xu -xv 2 2 ≤ U 2 uv ∀{u, v} ∈ E k≤K θ uvk (x uk -x vk ) ≥ L 2 uv .          (19)

27.3586

Table 5 Performance of Yajima's SDP on tiny. We report the edge errors Φ, Ψ , the CPU time, a 3D plot of the solution x tiny given in the PDB file versus the solution x DEMI found by solving the DEMI instance with x = x tiny and y given by the solution of the solver, and the corresponding DEMI error ∂(x, y) = min g,ρ

x -gρ(y) .

It should be clear that for each solution x * of Eq. ( 3), there is a parameter matrix θ * ∈ R mK such that x * is a feasible solution of Eq. ( 19): it suffices to choose

θ * uvk = (x * uk -x *
vk ) for each {u, v} ∈ E and k ≤ K. Note that Eq. ( 19) is a convex MP, and can therefore be solved efficiently. We let PtwCvx(θ) be the solution of Eq. ( 19) with input parameters θ.

A new i DGP algorithm

In this section we discuss an adaptation to the i DGP of the well-known MWU method [START_REF] Arora | The multiplicative weights update method: a metaalgorithm and applications[END_REF]. As explained in [START_REF] Arora | The multiplicative weights update method: a metaalgorithm and applications[END_REF], the MWU is in fact a meta-algorithm: it has been rediscovered along the years applied to many different optimization problems. Differently from most meta-heuristics, the MWU is as much a theoretical tool as a practical method, insofar as it provides a "generic" asymptotic performance guarantee which works for all problems where the MWU applies. The performance guarantee proof can be modified according to the specific features of the given problem to yield theoretical results. Among the problems listed in [START_REF] Arora | The multiplicative weights update method: a metaalgorithm and applications[END_REF], possibly the most interesting for the GO community are the Plotkin-Shmoys-Tardos LP feasibility approximation algorithm [START_REF] Plotkin | Fast approximation algorithm for fractional packing and covering problems[END_REF] and the SDP approximation algorithm in [START_REF] Arora | Fast algorithms for approximate semidefinite programming using the multiplicative weights update method[END_REF].

The MWU is applied to a multi-iteration setting over a given horizon {1, . . . , T } where, at each iteration t ≤ T , m "advisors" express an opinion about a certain decision. The advisors' opinion yield a gain/loss vector

ψ t = (ψ t i | i ≤ m) in [-1, 1] m .
The MWU method associates a discrete distribution ρ t = (ρ t i | i ≤ m) on the advisors, which is updated using the rule

ω t i = ω t-1 i (1 -ηψ t-1 i ) ( 20
)
for each t > 1, where

ρ t i = ω t i ω t i
and η ≤ 1 2 is a user-defined parameter. This distribution essentially measures the reliability of each advisor. The method then stochastically takes the decision given by advisor i with probability ρ t i . The average gain/loss made by MWU is therefore given by the weighted average Ω t = ψ t • ρ t . It is shown in [START_REF] Arora | The multiplicative weights update method: a metaalgorithm and applications[END_REF] that the following bound holds:

t≤T Ω t ≤ t≤T ψ t + η t≤T |ψ t | + ln m η , (21)
where is the index of the best advisor on average over all iterations. For fixed m and T → ∞, Eq. ( 21) states that the cumulative gain/loss made by the MWU method is bounded by a (piecewise) linear function of the gain/loss made by the best advisor, which is somewhat counterintuitive, given that is not known in advance.

The MWU method in the i DGP setting

We now reinterpret the MWU method in the setting of the i DGP, which aims to solve the problem via the pointwise reformulation Eq. ( 19). Consider a loop over T iterations: the convex pointwise reformulation Eq. ( 19) is solved at each iteration and efficiently yields a candidate realization x. This is then refined using x as a starting point to a local Nonlinear Programming (NLP) solver applied to the penalty minimization formulation of Eq. ( 13), which yields a current iterate x. We now explain how x is used to stochastically update θ at iteration t ≤ T along the lines of the MWU method (see the summary in Fig. 4):

let (Duv) = ( xu -xv | u, v ∈ V ) be the distance matrix corresponding to x; -for each {u, v} ∈ E and t ≤ T , let:

ψ t uv = αuv max {w,z}∈E αwz (22)
be the relative error of D with respect to [L, U ], where αuv is defined in Eq. ( 4) -note that ψ t is a scaled edge error vector with every component in [0, 1]; -for each {u, v} ∈ E and 1 < t ≤ T let

ω t uv = ω t-1 uv (1 -ηψ t-1 uv ); (23)
let θ uvk be a random value sampled from the uniform distribution on [0, ωuv(x ukx vk )]. We remark that the distribution ρ t is defined in terms of the edge weights ω t :

ρ t uv = ω t uv {w,z}∈E ω t wz . ( 24
)
The MWU method applied to the i DGP is given as Alg. 2.

θ x D ψ t x = PtwCvx(θ) D = EDM(x) error ψ t uv = αuv maxwz αwz scaled error θ uvk ∼ [0, ω t uv ψ t uv (x uk -x vk )
] ω t updated as per Eq. ( 23) Fig. 4 The update of θ from a candidate realization x at each iteration t of the MWU method. The oracle PtwCvx(θ) solves the pointwise reformulation Eq. ( 19) parametriezd with θ, and uses the solution as a starting point to a local NLP algorithm solving an exact formulation of the i DGP, say Eq. ( 13).

Algorithm 2 MultiplicativeWeightsUpdate(η, T )

1: let ω 0 = 1 2: let x be the output of a local NLP solver applied to Eq. ( 13) 3: let x = x be the best solution so far 4: for t ≤ T do 5:

derive θ from x as explained above 6:

compute a new candidate realization x = PtwCvx(θ) 7:

let x be the solution returned by a local NLP solver on Eq. ( 13) with x as starting point 8:

if x is an improvement with respect to x according to the average error Ω t , let x = x 9: end for 4.2 The MWU approximation guarantee for the i DGP One specific feature of the i DGP is that the "advisors" never yield gains but only a cost vector ψ t having components in [0,[START_REF] Alfakih | Solving Euclidean distance matrix completion problems via semidefinite programming[END_REF]. This allows us to prove the following result:

Proposition 2 After T iterations of the MWU method, the following relationship holds:

min t≤T Ω t ≤ 1 T   ln m η + (1 + η) min {u,v}∈E t≤T ψ t uv   . ( 25
)
Proof By Line 8 in Alg. Dividing through by T yields the result.

2

We remark that the RHS of Eq. ( 21) is the average weighted error of the best realization found by the MWU in T iterations. Prop. 2 states that this error is in the order of a linear function of the smallest scaled error (see Eq. ( 22)) over all edges.

Pointwise reformulation feasibility

Although the pointwise reformulation is exact for a certain value of θ, it may fail to even be feasible for certain other values of θ. Since this would be an issue for the MWU method, we further relax it to the following (always feasible) form: max

x,s {u,v}∈E k≤K

θ uvk (x uk -x vk ) -suv ∀{u, v} ∈ E xu -xv 2 2 ≤ U 2 uv ∀{u, v} ∈ E k≤K θ uvk (x uk -x vk ) ≥ L 2 uv -suv s ≥ 0.                ( 26
)
5 Computational assessment

The aim of this section is to present results obtained by four solvers (MS, VNS, MWU, and Mosek) over 19 different formulations, for each of 61 i DGP instances.

Since not every solver can be applied to every formulation, and sometimes errors are generated for combinations of solver+formulation with some of the instances, the number of measure vectors is less than 4 × 19 × 61.

Solver+formulation combinations

More precisely, we apply MS and VNS to Eq. ( 13) and its 4 variants (the square root variant and 3 explicitly listed ones), Eq. ( 14) and its square root variant, Eq. ( 15) and its positively weighted objective function variant, for a total of 9 formulations. We apply MWU to Eq. ( 19), and Mosek to Eq. ( 17) and its trace variant, and to Eq. ( 18). We therefore consider 22 different solver+formulation combinations. Unlike in the validation experiments, we did not consider the sBB solver as most instances are excessively difficult. The rest of the solver set-up is the same. The solvers MS, VNS, MWU, which are all implemented in AMPL, solve NLP subproblems at each iteration using the local NLP solver Ipopt. The SDP formulations were modelled using YalMIP running under MATLAB and solved using Mosek. Like the validation experiments, all results were obtained on an Intel i7 CPU running at 2.0GHz with 8GB RAM under the Darwin Kernel v. 13.3.0.

User-configurable parameters

Each of the MP solvers was given at most 20s of user CPU time, excluding the time taken by Ipopt. Each call to Ipopt was also limited to 20s; however, the Ipopt documentation warns that its stopwatch is not checked regularly, but only after certain operations, which on certain instances appear to take place very rarely. This is apparent in Table 9, where many solvers exceed the 20s CPU time limit. Mosek was given no time limit, since we wanted to find the optimal solution of the SDP.

All tolerances in the AMPL code were set to 1×10 -6 . Ipopt was used in its default configuration. The VNS maximum neighbourhood radius and the maximum number of local searches deployed in each neighbourhood were both set to 5. The η parameter in MWU was set to 0.5 (its maximum value) after some preliminary testing. Mosek was used in its default configuration.

Instances

Instances were obtained from a selection of PDB files by extracting all the atomic coordinates, computing all of the inter-atomic distances, and discarding all those distances exceeding 5 Å (so as to mimic NMR data). More precisely, covalent bonds and angles are known fairly precisely; since each covalent angle is incident to two covalent bonds, the remaining side of the triangle they define can also be computed precisely. Other known distances can be found through NMR experiments, which yield an interval measurement. We extracted the protein backbone from each considered PDB dataset, computed all precise distances, and then we replace all other distances duv smaller than 5 Å by the interval [duv -0.1duv, duv + 0.1duv].

The mean pruning group generator size |Z| over the test instances is 1.78 and the standard deviation is 4.92, but this is due to a single outlier with |Z| = 34. Removing the outlier, we have mean |Z| 1.04 and standard deviation 0.30, consistent with Sect. 2.3.2. The sparsity of the pruning edges over the test instances is 0.14.

Table 6 reports the instance names, their sizes, and whether they are classified as easy or hard (last column), see Sect. 5.5.

Weeding out obvious losers

Not every combination of solver and formulation variant is worth considering. Those which find a solution with high average edge error Φ and/or maximum edge error Ψ should be excluded. We proceeded to record Φ, Ψ , and seconds of user CPU time for every combination on every instance, and we computed the average values (over all instances) of Φ, Ψ , and CPU time.

The statistics for the MS, MWU, and VNS solvers are shown in Fig. 5 (more precisely, if µ is an average, we plotted log(1 + µ)). All variants involving square roots perform really poorly in terms of edge errors. The statistics for the Mosek solver, limited to instances where n ≤ 200 because of RAM limitations, are given below. The relevant figure in this table is that the SDP relaxation sdprel has much lower average edge error than the other formulations, lower maximum error, and slightly higher CPU time.

"! "#$! "#%! "#&! "#'! "#(! "#)! "#*! "#+! "#,! $! "! "#%! "#'! "#)! "#+! $! $#%! $#'! "! "#(! $! $#(! %! %#(! &! &#(!
These tests show that, on average, the SDP trace variant, Yajima's relaxation, and all square root variants are not worth considering. The reason why introducing square roots results in performance losses may be related to the use of the same local subsolver (Ipopt) within all global optimization solver, since it carries out most floating point computations.

A remark about Yajima's relaxation: although it was introduced specifically for the i DGP, it was originally solved using an ad-hoc interior point method. Even though our results show it underperforms on average with respect to Mosek, this does not negate the (good) results reported in [START_REF] Yajima | Positive semidefinite relaxations for distance geometry problems[END_REF].

We call bad the solver+formulation combinations we excluded, and good the rest. The good combinations are shown below, marked by a "1" in the corresponding entry.

Formulation Solver

Description Notation Name MS MWU VNS Mosek (13) (13)
Idgp1 1 1 (13) variant (i) [START_REF] Biswas | Semidefinite programming based algorithms for sensor network localization[END_REF].1

Idgp1var1 1 1 (13) variant (ii) (13).2 Idgp1var2 1 1 (13) variant (iii) (13).3 Idgp1var3 1 1 (14) (14)
Idgp3

1 1 (15) (15)
Idgp4 1 1 (15) variant (i) [START_REF] Candès | PhaseLift: Exact and stable signal recovery from magniture measurements via convex programming[END_REF].1

Idgp4var1 1 1 (19) (19) Imwu 1 (17) (17) sdprel 1 5

.5 Focusing on the hard instances

We also make a qualitative distinction between easy and hard instances. We call an instance easy if at least one third of the good combinations find a solution with Φ, Ψ approximately zero within 1s of user CPU time, and hard the rest. The classification is reported in the last column of Table 5: hard instances are marked "H". We marked H * the instances which are "borderline hard", i.e., there is at least one good combination which finds a solution with Φ, Ψ approximately zero within 1s of user CPU time. The computational results below will focus on the hard instances for Φ, Ψ ; because of excessive computational requirements, however, we shall relax this constraint for the results on the DEMI measure ∂.

Testing heuristics without averages

When benchmarking heuristic algorithms, such as MS, VNS, or MWU, it is customary to present results based on a number of runs (the higher the better) of the same instance. Because of the complexity of this computational comparison, and the absolute time taken to perform it, it was ungainly for us to multiply this effort by a significant factor (say 10 or 100). Does this mean that our results are unreliable? Though it could be argued that the instance-by-instance results are in fact unreliable, as can be gleaned by the difference in ∂ measure for the tiny instance in Sect. 3 and those in Table 10, we think the averages (reported in Tables 78910) are not. Since we never claim in our computational comparisons that one method is best for a certain instance, but only suggest first and second best over all tested instances, we think our computational benchmark is significant.

Comparative results on edge errors and CPU

In this section we discuss an overarching comparison yielding an overall "winner". Our most meaningful measure, if Φ and Ψ are nonzero, is the DEMI measure ∂(•, y), where y is a given solution of the K DMDGP instance being solved. By Sect. 2.3.4, however, we are not able to compute it for every instance, and hence we focus on Φ, Ψ for our global comparison, and only look at δ on a subset of instances (Sect. 5.8).

Tables 7-9 report the average edge errors Φ, the maximum edge error Ψ , and the CPU time taken by the good combinations when solving hard instances. We remark that the MWU algorithm is best with respect to the edge errors Φ and Ψ , and the worst with respect to CPU time. However, since CPU time is of least consequence in protein conformation computations, CPU time information has a much lower priority than solution quality. We can therefore make the following claim.

The MWU algorithm is the best solver on average.

Given the consequential CPU time difference between MWU and the other solvers, it is worth ranking the solver+formulation combinations by Φ, Ψ , and CPU time (see below). This ranking shows that mwu+Imwu has the only consistent ranking in both Φ and Ψ . It also shows that no other solver+formulation combination has the same desirable property of approximately equal rank w.r.t. both Φ and Ψ . The issue is not only relative: values of Φ higher than 0.1 and of Ψ higher than 1.5 may well imply that the realization is fundamentally wrong, and the only combinations with Φ < 0.1 and Ψ < 1.5 are ms+Idgp3, vns+Idgp3, mosek+sdprel. However, the statistics for the latter were computed on a subset of instances (all those with n ≤ 200) due to the high RAM requirements of Mosek when applied to large instances (see Sect. 5.4). Based on these observations, we claim that: the formulation Idgp3 in Eq. [START_REF] Biswas | Semidefinite programming approaches for sensor network localization with noisy distance measurements[END_REF], when used with MS or VNS, is second best.

Rank

We observe that the usual trade-off between quality and efficiency is also at play: solving Eq. ( 14) takes longest over all formulations solved by both MS and VNS.

Results on DEMI

Table 10 reports the results on the DEMI measure. Note that the instances in the test set are not the same as for the tests on Φ, Ψ , and CPU (Tables 789). As mentioned in Sect. 2.3.4, it is not always possible to determine a cTOP order automatically (or disprove that one exists) in acceptable amounts of CPU time, which is a requirement for computing the DEMI measure. Table 10 includes all instances for which this task could be carried out within 150s of CPU time.

Although it is clear that the SDP relaxation Eq. ( 17) scores the best performance in terms of the DEMI measure, we mentioned above that the Mosek solver is unable to scale up to desired sizes. We must therefore resort to the second best, which happens to be the MWU algorithm, consistently with Sect. 5.7. We also observe that VNS attains lower average DEMI measure values more often than MS.

We recall that the DEMI measure values for tiny differ from those given in Sect. 3 for the reasons given in Sect. 5.6.

Conclusion

Our main aim is to find the best general-purpose continuous search methods for solving i DGP instances. To answer this question, we need: (i) a set of benchmarking measures; (ii) a set of i DGP formulations; (iii) a set of methods; (iv) extensive computational results. Since a preliminary study [START_REF] Liberti | Solving large-scale distance geometry problems exactly versus approximately[END_REF] showed that two standard metaheuristics and the existing benchmark measures were insufficient, we decided to introduce a new measure and a new method.

Accordingly, this paper presents several notions: (a) a coordinate root mean square deviation modulo partial reflections (called DEMI measure), for benchmarking the performance of i DGP algorithms on protein isomers; (b) a zoo of mathematical programming formulations for the i DGP; (c) a new method for solving the i DGP, based on the well-known Multiplicative Weights Update (MWU) algorithm; (d) a complex computational benchmark for the best formulation-based methods on the hardest instances.

Our study shows that, on average:

the new MWU-based heuristic yields i DGP solutions of highest quality with respect to existing measures; -the Square Factoring formulation in Eq. ( 14) is second best; -as concerns the new DEMI measure, the SDP relaxation in Eq. ( 17) is best, but only on a limited set of instances, whereas the MWU-based heuristic is second best.

Future research directions for the topics presented in this paper include: (i) the algorithmic exploitation of the DEMI measure for more effective pruning within the Branch-and-Prune algorithm; (ii) the insertion of a limited diving device within the Branch-and-Prune: instead of branching in order to find possible positions of the next atom in the order, it would be desirable to realize a considerable number of successive atoms by means of one of the continuous methods presented in this paper. 6 The test set: 61 instances, from the PDB and [START_REF] Lavor | On generating instances for the molecular distance geometry problem[END_REF], their sizes, and the estimated difficulty of solution.

Instance

Fig. 1

 1 Fig.1In each picture: mean (top curve) and standard deviation (bottom curve) of the pruning group size as a function of n for fixed values of K = 2 (left column), K = 3 (right column), and the edge sparsity s (values in {0.1, 0.2, 0.3} in top, middle and bottom rows).

Fig. 2

 2 Fig.2In each picture: mean (top curve) and standard deviation (bottom curve) of the pruning group size as a function of the edge sparsity s for fixed values of K = 2 (left column), K = 3 (right column), and n (values in {10, 15, 20} in top, middle and bottom rows).

Fig. 3

 3 Fig.3The tiny instance: a heat map of the pEDM (upper left) and the correct realization in R K shown by the Jmol molecular visualization software (lower left) and in a Euclidean space plot, using the natural vertex order (right). The axes of the two 3D plots are not aligned to minimize overlap. The atom which appears disconnected in the Jmol plot corresponds to vertex 28 in the Euclidean plot, and the nine atoms in a pentagonal arrangement correspond to vertices 29-37.

Table 2

 2 Performance of square factoring on tiny. For each solver, we report the edge errors Φ, Ψ , the CPU time, a 3D plot of the solution x tiny given in the PDB file versus the solution x DEMI found by solving the DEMI instance with x = x tiny and y given by the solution of the solver, and the corresponding DEMI measure ∂(x, y) = min g,ρ

Fig. 5

 5 Fig. 5 Histogram plots of the statistic log(1 + µ) whenever µ is the average of Φ (top), Ψ (middle), and CPU time (bottom) over all instances, for each relevant combination of solver+formulation, with "solver" in MS (left), MWU (middle) and VNS (right).

  .

				Original			Var. (i)
	Solver	Φ	Ψ	CPU	Φ	Ψ	CPU
	Couenne	0	0.03	1.78	0	0.03	1.53
	xtiny
	and
	xDEMI

  t ) associated to x . From Eq. (21), because ψ t uv ≥ 0 for all {u, v} ∈ E, t ≤ T , we get ψ t uv = |ψ t uv |, whence, by definition of in Eq. (21):Since x is the realization with lowest error over all t ≤ T , then T min

		{u,v}∈E	t≤T	ψ t uv +	ln m η	.
	t≤T	Ω t ≤ (1 + η) min {u,v}∈E	t≤T	ψ t uv +	ln m η	.

2, min t≤T Ω t is the per-edge error (weighted by the distribution p t≤T Ω t ≤ t≤T Ω t , which implies: T min t≤T Ω t ≤ (1 + η) min

Table 7 Φ

 7 statistics: blue indicates best.

	vns	Idgp4var1	3.81	3.71	1.19	1.0	3.03	3.59	2.57	3.58	0.314	0.313	0.142	0.419	3.85	3.52	0.369	0.332	0.508	0.978	0.35	3.11	2.63	2.22	2.72	3.55	2.68	0.385	3.86	2.027
	vns	Idgp4	3.62	3.5	1.33	0.948	1.0	3.76	3.22	3.42	0.272	0.272	0.0856	0.55	3.54	3.84	0.374	0.4	0.362	3.09	2.72	3.0	3.24	2.62	2.63	3.09	2.32	0.334	4.23	2.140
	vns	Idgp3	2.58	2.79	0.00	0.101	0.08	3.04	0.81	1.78	0.953	1.04	0.00	0.635	1.76	2.15	0.00	0.00	0.00	1.51	0.887	0.824	2.3	2.08	1.65	1.8	1.72	0.00	4.1	1.281
	vns	Idgp1var3	3.7	3.0	0.0629	1.22	1.75	3.51	2.48	3.72	0.00	0.911	0.00	1.19	3.65	3.88	0.00	0.00	0.00	1.44	3.56	2.1	2.94	2.12	3.68	2.9	2.55	0.00	3.82	2.007
	vns	Idgp1var2	3.9	4.01	0.345	0.44	1.62	2.76	2.48	3.42	0.00	0.00	0.00	0.00	3.39	3.39	0.00	0.00	0.314	1.7	2.66	2.47	2.67	2.07	3.35	1.87	2.77	0.00	4.3	1.849
	vns	Idgp1var1	2.05	1.93	0.053	0.0846	0.256	2.01	1.4	2.55	1.71	0.618	0.00	0.309	2.36	2.12	0.00	0.00	0.00	1.28	1.96	2.16	2.04	1.25	2.42	1.08	1.78	0.00	2.57	1.259
	vns	Idgp1	4.29	3.28	0.36	0.38	1.27	3.37	1.93	3.51	0.00	0.00	0.00	1.13	3.3	3.52	0.00	0.00	0.00	0.295	2.39	2.47	2.75	3.21	3.19	2.73	0.11	0.00	3.82	1.752
	mwu	Imwu	3.05	2.66	0.143	0.453	0.95	1.21	1.45	1.62	0.00	0.00	0.00	0.00117	1.67	2.77	0.00	0.314	0.00	0.928	1.99	2.19	2.3	0.00	2.53	0.00	0.00	0.00	3.77	1.111
	ms	Idgp4var1	3.85	3.76	1.36	0.677	1.58	2.38	2.07	4.0	0.254	0.211	0.176	0.312	3.84	3.56	0.418	0.307	0.368	0.29	3.02	3.2	3.21	2.58	3.17	3.17	2.81	0.318	3.86	2.028
	ms	Idgp4	4.05	3.53	0.965	1.23	1.49	3.32	3.35	3.59	0.272	0.272	0.0856	0.31	3.27	3.76	0.414	0.4	0.362	1.03	2.02	3.02	2.82	3.19	2.91	2.91	2.8	0.334	4.03	2.064
	ms	Idgp3	2.47	2.12	0.0603	0.06	0.151	2.59	0.89	1.35	0.304	0.00	0.00	0.00	2.64	3.65	0.00	0.00	0.00	2.26	1.62	0.82	1.86	1.2	2.26	1.78	1.16	0.00	4.9	1.265
	ms	Idgp1var3	3.91	3.56	0.517	0.813	1.29	2.7	2.01	3.74	0.00	0.00	0.00	1.54	3.57	3.57	0.00	0.00	0.00	1.77	2.59	3.36	2.59	2.16	2.81	3.28	2.1	0.00	4.46	1.939
	ms	Idgp1var2	3.45	2.87	0.0667	0.45	0.912	3.57	2.1	2.75	0.00	0.00	0.00	0.32	0.00	2.99	0.00	0.00	0.00	0.807	1.47	2.89	2.68	2.79	3.3	0.867	3.66	0.00	4.17	1.560
	ms	Idgp1var1	2.09	2.14	0.0167	0.233	0.564	2.13	1.86	2.35	0.00	0.406	0.00	0.505	2.59	2.69	0.00	0.00	0.00	1.86	0.699	1.03	1.83	2.26	2.07	1.35	2.06	0.00	2.66	1.237
	ms	Idgp1	3.21	3.31	0.332	0.394	1.48	3.62	1.99	3.83	0.00	0.00	0.00	0.00	3.16	3.39	0.00	0.00	0.00	0.845	3.43	2.85	2.49	1.42	3.29	2.8	3.39	0.00	4.13	1.828
	mosek	sdprel	NA	NA	NA	3.2	2.97	NA	0.898	1.27	0.546	0.546	0.443	0.474	NA	NA	0.959	1.42	2.1	0.951	1.66	NA	NA	NA	NA	NA	NA	0.306	NA	1.267
	Instance	100d	1PPT	1guu	1guu-1	1guu-4000	2kxa	C0020pdb	C0030pkl	C0080create.1	C0080create.2	C0150alter.1	GM1 sugar	cassioli...	helix amber	lavor30 6-2	lavor30 6-3	lavor30 6-4	names	pept	res 0	res 1000	res 2000	res 2kxa	res 3000	res 5000	tiny	water	Average

Table 8 Ψ

 8 statistics: blue indicates best.

  Table 10 DEMI measure statistics: blue indicates best. Although the best on average is Mosek on sdprel, this combination was unable to scale up to desired sizes. We therefore also emphasized the second best: MWU on Imwu.

	vns	Idgp4var1	98.386	242.788	3.403	106.075	2.910	4.876	10.781	27.363	26.527	13.691	2.752	1.048	2.874	3.653	5.932	22.334	8.709	34.898	19.329	28.453	43.134	46.677	0.460	0.660	136.753	60.485	118.871	names 35.297	lavor30 6-4 165.878	82.487	17.314	7.964	1382.762
	vns	Idgp4	182.382	201.001	2.841	101.206	3.028	9.485	9.485	20.498	30.645	20.498	3.232	2.924	3.232	3.232	2.960	21.203	12.306	41.663	5.436	26.834	29.950	45.894	0.460	0.660	79.722	121.924	134.238	38.168	3.05 36.592	44.655	30.645	2.651	1269.650
	vns	Idgp3	313.398	215.186	16.053	82.440	0.250	2.549	17.623	24.708	1.799	24.647	0.056	0.075	0.096	0.056	0.136	15.448	0.243	16.082	10.353	16.565	20.193	29.897	0.119	0.025	196.041	77.778	86.838	104.359	1.34 121.108	103.984	23.558	1.864	1523.527
	vns	Idgp1var3	242.633	126.893	10.312	104.147	0.240	15.183	0.462	24.686	19.982	24.777	0.109	0.348	0.603	0.064	6.638	16.135	17.135	2.153	15.494	13.133	2.035	2.086	0.655	0.033	131.249	38.340	175.189	118.709	0.653 70.533	61.313	24.689	7.218	1273.176
	vns	Idgp1var2	248.200	172.713	0.221	152.011	5.464	7.142	25.227	58.306	36.257	23.424	4.267	0.485	1.487	4.028	5.603	35.156	0.241	38.034	16.838	15.800	41.153	24.175	0.037	0.033	149.057	85.413	95.563	64.137	1.45 134.721	99.729	62.995	11.334	1619.251
	vns	Idgp1var1	112.595	218.604	0.210	98.227	0.246	0.848	0.422	19.999	19.998	4.451	0.047	0.080	0.681	0.053	6.634	2.286	10.835	16.878	15.509	1.838	40.102	2.136	0.345	0.224	137.643	119.482	115.147	90.640	0.31 44.590	125.495	24.687	8.322	1239.254
	vns	Idgp1	121.270	135.907	26.119	51.538	2.598	23.890	27.733	25.222	21.885	19.770	2.203	0.084	0.379	0.076	0.077	14.949	28.764	41.242	1.045	23.498	42.098	44.276	0.338	0.463	136.851	46.920	41.158	110.327	1.94 117.402	44.859	57.688	4.406	1215.035
	mwu	Imwu	132.709	153.964	0.208	15.169	0.564	35.427	9.005	18.467	26.072	21.049	4.274	7.366	4.277	6.555	6.642	26.190	29.555	55.839	18.840	44.336	52.537	44.294	0.445	0.707	75.056	99.926	0.732	149.216	20.0 9.557	6.202	2.307	21.402	1078.889
	ms	Idgp4var1	196.529	161.057	2.302	64.190	2.158	7.726	29.485	28.260	33.841	31.231	1.886	2.901	3.237	3.538	7.190	24.563	24.558	7.342	4.149	26.800	17.784	48.735	0.460	0.660	92.769	142.391	111.010	90.800	20.0 38.559	102.613	28.181	3.720	1340.625
	ms	Idgp4	127.979	184.057	2.841	138.700	3.028	9.485	9.485	20.498	30.645	30.645	3.232	2.924	3.232	3.232	2.960	21.203	25.772	41.663	5.436	26.834	29.950	45.894	0.460	0.660	101.755	114.645	139.965	83.657	7.46 80.058	99.724	20.498	2.651	1413.768
	ms	Idgp3	256.755	209.438	26.119	74.355	0.522	15.159	15.156	2.191	21.033	26.192	0.057	0.079	0.058	2.130	0.942	14.926	11.120	34.248	7.403	26.029	32.357	12.187	0.116	0.026	46.055	122.709	97.516	145.808	1.59 82.502	3.62 100.349	25.506	18.246	1427.289
	ms	Idgp1var3	158.154	138.726	26.119	107.329	0.610	15.474	7.391	26.033	20.131	19.257	3.813	1.154	4.273	0.215	4.966	13.649	0.253	30.305	4.558	1.847	2.443	44.901	0.557	0.038	157.351	170.710	176.975	82.791	2.67 93.328	1.84 51.874	23.036	2.189	1390.450
	ms	Idgp1var2	145.938	181.700	26.118	59.612	3.412	27.131	7.809	49.372	40.674	57.546	6.800	0.649	3.730	0.064	7.131	30.050	1.565	34.249	12.490	25.267	41.597	42.796	0.120	0.037	120.930	99.962	130.671	94.618	1.55 48.903	3.14 105.803	23.329	18.174	1448.247
	ms	Idgp1var1	163.411	210.966	26.066	109.387	0.403	15.052	7.389	26.107	24.602	3.314	0.067	0.076	5.905	0.072	0.128	13.647	10.833	16.883	18.835	15.159	2.035	2.041	0.190	0.066	149.633	82.179	125.860	72.845	6.88 106.614	2.6 122.206	14.138	5.758	1351.867
	mosek ms	sdprel Idgp1	132.083 116.038	228.757 202.573	4.203 0.205	7.954 104.331	2.105 0.511	5.690 38.839	5.690 0.520	5.566 38.284	5.566 1.795	5.566 40.742	5.970 4.326	6.509 0.066	5.970 4.274	5.970 0.194	5.103 0.135	32.441 32.157	28.787 8.366	37.932 42.267	16.717 5.142	22.715 31.712	32.540 41.196	10.389 44.385	0.460 0.894	1.423 0.054	7.933 206.560	8.151 24.677	13.866 202.930	11.008 106.131	0.332 9.294 0.412 144.285	11.9 2.61 7.633 101.283	5.566 31.324	2.397 17.715	681.954 1593.911
	Instance	1guu-1	1guu	2erl-frag-bp1	2kxa	C0150alter.1	C0700.odd.G	C0700.odd.H	C0700odd.C	C0700odd.D	C0700odd.E	lavor11 7-1	lavor11 7-2	lavor11 7-b	lavor11 7	lavor11	lavor30 6-1	lavor30 6-2	lavor30 6-3	lavor30 6-4	lavor30 6-5	lavor30 6-7	lavor30 6-8	mdgp4-heuristic	mdgp4-optimal	res 0	res 1000	res 2000	res 2kxa	0.37 res 3000	2.08 res 5000	small02	tiny	Averages

Acknowledgments

We are grateful two the Editor-in-Chief for simplifying a technical argument, and to two anonymous referees for helping us improve this paper. The second author (VKK) is supported by a Microsoft Research PhD Fellowship. The third author (CL) is grateful to the Brazilian funding agencies FAPESP and CNPq for financial support. The fourth author (LL) is partly supported by the ANR grant "Bip:Bip" under contract ANR-10-BINF-0003. The fifth author (NM) is grateful to the Brazilian funding agencies FAPERJ and CNPq for financial support.