iterates until an equilibrium [w. r. t. ]{}the current temperature is reached—here controlled by the number of iterations and modifications. As we do not want to get completely different solutions for reasons mentioned above, we choose a low start temperature and decrease it rather quickly.

Within the innermost loop a new neighbor solution is computed. In fact, we use parallelism here to reduce the running time of the algorithm. While this can lead to some data races if the position of a vertex is altered by more than one thread, we did not experience any significant decrease in quality. The number of total iterations, steps with no improvement and the number of modifications are all chosen rather small to keep the running time low.

The main ingredients of the innermost loop are (i) the local error criterion, (ii) the local optimizer that computes a neighbor solution, and (iii) the acceptance function.

We define $\text{error}_{vw}(x)$ as $\text{error}_{vw}(x) \coloneqq \max \{ l_{vw} - \lVert x_v - x_w \rVert, \lVert x_v - x_w \rVert - u_{vw} , 0\}^2.
$ and the local error of an edge $\{v,w\}$ as: $$\text{localError}(\{v,w\}, x) \coloneqq \text{error}_{vw}(x) + \sum_{\mathclap{u \in N(v) \setminus \{w\}}} \text{error}_{vw}(x) + \sum_{\mathclap{u \in N(w) 