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?
Asked By : cagirici
Answered By : D.W.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48949
0 comments:
Post a Comment
Let us know your responses and feedback