7
$\begingroup$

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?

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.
$\endgroup$
14
  • $\begingroup$ are you doing this in 3d? there are many standard algorithms. is there some reason convex optimization is preferred? $\endgroup$
    – vzn
    Nov 2, 2015 at 3:31
  • $\begingroup$ @vzn I am working on 2D. Because of research purposes, I need to model it as CSP, LP and ILP. First step is to find a convex formulation $\endgroup$
    – padawan
    Nov 2, 2015 at 6:26
  • 1
    $\begingroup$ Regarding the edited question: the constraint $|{O^X}_{ij}| + |{O^Y}_{ij}| = w_{ij}$ is not correct. You want $|{O^X}_{ij}|^2 + |{O^Y}_{ij}|^2 = w_{ij}^2$, which is not the same. For instance, $1+1=2$, but $1^2+1^2 \ne 2^2$. So, the constraints you have written down are not equivalent. (A secondary problem is that the equation with absolute value is not convex, I think.) $\endgroup$
    – D.W.
    Nov 2, 2015 at 19:59
  • $\begingroup$ @D.W. it is indeed not the same but this constraint holds for integer coordinates and integer edges. Unfortunately, I don't get a proper solution yet, even though it gives a solution. $\endgroup$
    – padawan
    Nov 2, 2015 at 20:39
  • 1
    $\begingroup$ @vzn I think you what you are saying is minimize $|(x_i - x_j)^2 + (y_i - y_j)^2 - w_{ij}^2|$ $\endgroup$
    – padawan
    Nov 5, 2015 at 20:38

2 Answers 2

4
+50
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

the 2d case of "graph embedding" is also known simply as "graph drawing" and there is a very wide variety of techniques. the most common is probably force directed graph drawing. however heres a basic survey/ slide show that describes CSP, LP, ILP techniques in general. again there is large diversity and there does not really seem to be a unique or standard way to apply them in this area. the techniques generally find approximate solutions that roughly correlate edge weights to Euclidean distances (basically your problem). it is up to the designer to balance tradeoffs in this accuracy with other constraints of the drawing. some particular area of this research may better match your requirements if you are better able to specifically/ define/ articulate them and looking at other standard/ "typical" algorithms in the area can help you do that.

$\endgroup$
5
  • 1
    $\begingroup$ This does not seem to answer the question. (I think such a general background answer is much better as a comment.) $\endgroup$
    – Juho
    Nov 2, 2015 at 16:19
  • $\begingroup$ so then regard it as an "extended comment". anyway afaict the original question is not specific enough to give specific answer. the answer matches the basics of the question. eagerly await any better answer. $\endgroup$
    – vzn
    Nov 2, 2015 at 16:37
  • $\begingroup$ Thank you for this background survey! However, as far as I'm concerned, graph embedding is a restricted case for graph drawing that only deals with Euclidean geometry. $\endgroup$
    – padawan
    Nov 2, 2015 at 17:21
  • $\begingroup$ huh? by defn graph drawing uses euclidean geometry... euclidean geometry is a restricted case for graph embedding. isnt your problem for 2d euclidean geometry? $\endgroup$
    – vzn
    Nov 2, 2015 at 17:32
  • $\begingroup$ @vzn Yes, you are right. I meant the other way around. $\endgroup$
    – padawan
    Nov 2, 2015 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.