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 sentenceHow 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 questionThere 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 questionI 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?I came up with something:Assuming that the coordinates and the edge weights will be integers;I add two more decision variables: $O^X = \{{O^X}_{12}, {O^X}_{13}, \dots, {O^X}_{21}, {O^X}_{23}, {O^X}_{|V|(|V|-1)}\} $ and  $O^Y = \{{O^Y}_{12}, {O^Y}_{13}, \dots, {O^Y}_{21}, {O^Y}_{23}, {O^Y}_{|V|(|V|-1)}\}$ where ${O^X}_{ij}$ is the offset of the $x$ coordinate of a node $j$ with respect to node $i$. The same goes with $y$ coordinates as well.For instance, if $x_i = 3$, $y_i = 4$, ${O^X}_{ij} = 2$, ${O^Y}_{ij}j = -1$ then $x_j = 5$ and $y_j = 3$.As for the constraints, I have written:\begin{matrix}\forall \{i,j\} \in E;\\x_j = x_i + {O^X}_{ij}\\y_j = y_i + {O^Y}_{ij}\\|{O^X}_{ij}| + |{O^Y}_{ij}| = w_{ij}\end{matrix}My logic behind that approach is as follows:Since all the coordinates are integers, we are able to assume that we place the graph on a grid.If the Euclidean distance between $i$ and $j$ is $2$, and $i$ is on $(x,y)$ point, then $j$ should be on one of the following:\begin{matrix}(x-2,&y+0)\\(x-1,&y-1)\\(x-1,&y+1)\\(x+0,&y-2)\\(x+0,&y+2)\\(x+1,&y-1)\\(x+1,&y+1)\\(x+2,&y+0)\end{matrix}Of course, this is just an approximation to the actual solution.However, the tool I work with (IBM ILOG CPLEX) does not give a solution.I think I am mistaken somewhere.**Note:** The above model (entitled as I came up with something is **not** what I am trying to achieve.However, I could not find a better way to impose convex constraints.
How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?
graph theory;weighted graphs;modelling;constraint programming
You can't. You can't express this without using quadratic constraints.  Your requirement is about Euclidean distance.  The Euclidean distance is inherently quadratic.  To be more precise about that: the problem cannot be expressed using solely using linear constraints, as the Euclidean distance is non-linear.That said, you can solve your one-sentence question directly, if you remove the requirement to use constraint programming.  The basic technique is to use triangulation.  I'll illustrate this below.Suppose that you know point $p_1$ is at $(0,0)$ and point $p_2$ is at $(0,5)$, and you know $d(p_1,p_4)=r$ and $d(p_2,p_4)=s$ where $r,s$ are given; you want to find the location of $p_4$.  This can be found using some simple algebraic manipulations.  Let $p_4$ be at coordinates $(x,y)$.  Then by the definition of the Euclidean distance, we have$$\begin{align*}r^2 &= x^2 + y^2\\s^2 &= x^2 + (y-5)^2.\end{align*}$$Subtracting the two equations, we get$$r^2 - s^2 = y^2 - (y-5)^2.$$Simplifying the right-hand side and then solving for $y$, we find$$y = (r^2 - s^2 + 25)/10.$$Plugging this into the definition of $r$, we also find$$x = \pm \sqrt{r^2 - y^2}.$$Thus, in this way you can compute the coordinates $(x,y)$ of $p_4$ (up to reflection) from the distances $r,s$ using a bit of simple algebra.So, if you have a point $p_4$ at some unknown location, and you know its distance to two other points at known locations, you can find the location of $p_4$ using triangulation.  Strictly speaking, we have found two possible candidates for the location of $p_4$ (modulo a reflection across the line from $p_1$ to $p_2$), but if we know the distance from $p_4$ to any third point we can try both possibilities and figure out which one of those two candidates is correct.The same techniques can be used to solve your very short version of the question.  We know the location of $p_1,p_2$, and for each other point, we know its distances to $p_1$ and $p_2$, so we can calculate its location.  Again, the problem becomes simple if we are allowed to use algebraic manipulations, rather than being forced to express it as a constraint system.Your detailed version of the problem is a different problem entirely.  If you have a complete graph -- or you have three points that are connected to all other points -- you can use the techniques outlined above.  (You can fix locations for those three points, and then derive the location of all other points using the methods above.)But if you have an arbitrary graph, the above techniques might not be enough.  I don't believe your general problem can be expressed as a constraint program with only convex constraints: I think it's a non-convex problem.  I don't have a proof of that, though.