Approximate euclidean graph from distance matrix?

Question

In a personal project of mine, I have been faced with the following problem. I have an $n \times n$ matrix $T$ where an entry $t_{ij} \geq 0$ denotes an arbitrary metric between two points $i$ and $j$ in the 2D Euclidean space.

What I would like to do is create a graph $G=(V,A)$ which can approximate matrix $T$ where $|V|=n$. The goal is to assign coordinates $(x_i,y_i)$ for each point $i \in V$. This should be done in such a way that the Euclidean distance $d_{ij}$ between $i,j \in V$ defined as

$d_{ij} = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}$

should approximate $t_{ij}$ as much as possible. Hence:

$d_{ij} \approx t_{ij}$

There is one additional constraint: the points need to be placed within a circle of radius $R$.

So far I have tried to approach this problem from a mathematical programming point-of-view. Unfortunately, my experience is mostly with linear programming but the problem I have at hand appears to be non-linear. Here is the model I have developed, where $x_i$ and $y_i$ are real-valued variables.

$\min \sum_{i \in V}\sum_{j \in V}|d_{ij}-t_{ij}|$

$\text{s.t. }$

$d_{ij} = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}$

$d_{0j} \leq R,\ \forall\ j \in V,\ \text{0 refers to coordinate } (0,0)$

$x_i,y_i \in [-R,R],\ \forall\ i \in V$

This way we know that an optimal solution would exist when the objective function is exactly 0.

However, I still have open questions which I cannot seem to find the answer to:

1. Is this the best way to model such problem?
2. How can I solve this model? Are there algorithms or solvers (e.g., CPLEX) for such model?
3. Does this problem already exist with some name in the literature?

Can anyone shed some light on this problem?

Answer 1

The exact version of your problem, where the distances are known exactly and the goal is to exactly match those distances, is known as the distance geometry problem. The approximate version, as you formulate it, seems similar to the multidimensional scaling problem.

The approach you sketch looks like a reasonable approach to the problem, and I imagine you could use any optimization method to try to minimize your objective function, including gradient descent or Newton's method. The initial placement of points might make a big difference to the quality of the solution so you might try making many runs with different random initializations, and keep the best solution you've found so far.

You could also try adapting force-directed graph drawing to your problem. You have a preferred distance $t_{ij}$ between each pair of vertices $i,j$, so you can treat this as a spring that exerts a force if its length is larger than $t_{ij}$ or smaller than $t_{ij}$.

See also https://softwareengineering.stackexchange.com/q/243199/34181, https://mattermodeling.stackexchange.com/q/5088, https://scicomp.stackexchange.com/q/40855/4274, https://math.stackexchange.com/q/156161/14578, https://mathoverflow.net/q/97611/37212, https://mathoverflow.net/q/7794/37212, https://math.stackexchange.com/q/3047212/14578.