Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example.
What I am trying to achieve with one sentence
How can I answer the following question by using constraint programming:
The Euclidean distances between a point $p_4$ and points $p_1(0,0)$, $p_2(0,5)$ and $p_3(5,0)$ are $5.00$, $3.16$ and $4.47$ respectively. Where is $p_4$ on the $xy$-plane?
without using quadratic constraints?
Very short version of the question
There are five points placed on a 2D plane.
We only know the pairwise distance between these points.
\begin{matrix} d_{12} &= 5.00\\ d_{13} &= 5.00\\ d_{14} &= 5.00\\ d_{15} &= 5.00\\ d_{23} &= 7.71\\ d_{24} &= 3.16\\ d_{25} &= 4.47\\ d_{34} &= 4.47\\ d_{35} &= 3.16\\ d_{45} &= 1.41\\ \end{matrix}
In addition, we know the coordinates of first three points.
\begin{matrix} p_1 &= &(0,0)\\ p_2 &= &(0,5)\\ p_3 &= &(5,0)\\ \end{matrix}
And we want to find the coordinates of remaining two:
\begin{matrix} p_4 &= &(3,4)\\ p_5 &= &(4,3)\\ \end{matrix}
How can I formulate this problem without using quadratic constraints? Note that in order to impose the Euclidean distance between two points, we need to use square of differences.
Detailed version of the question
I am trying to formulate the graph embedding problem as constraint satisfaction problem.
Graph embedding is simply assigning coordinates to the vertices of a graph by considering edge weights, where the weight $w_{ij}$ of an edge $\{i,j\}$ determines the Euclidean distance between the nodes $i$ and $j$.
My decision variables are two arrays, $X$ and $Y$. $X_i$ and $Y_i$ are the $x$ and $y$ coordinates of node $i$.
The mathematical model can be written as:
given: $G = (V,E)$
decision variables: $X = \{x_1, \dots, x_{|V|}\}$; $Y = \{y_1, \dots, y_{|V|}\}$
subject to: $\forall \{i,j\} \in E$; $(x_i-x_j)^2 + (y_i-y_j)^2 = w_{ij}^2$
As discussed here,
$(x_i-x_j)^2 + (y_i-y_j)^2 = w_{ij}^2$
is a non-convex constraint. Is there any way to formulate this problem using convex constraints?