# Modeling a lower-bound constraint on a euclidean distance in quadratic programming

 0 Hello, I have been trying to model a certain problem into a mainly linear program, but with some quadratic constraints since I don't think that is something that can be avoided. I hope to solve it either with Gurobi or CPLEX. I'm having a really hard time modeling the last, but crucial, part of the model. I have continuous variables that represent the positions of a known number of points in the $$\mathbb{R}^2$$ plane : they vary in a given $$B=[x_\text{min},x_\text{max}]\times [y_\text{min},y_\text{max}]\subset \mathbb{R}^2$$ box. For each couple of points $$(p,p')\in B^2$$, I'm interested in having a binary variable $$u_{pp'}$$ that would be equal to 1 if and only if $$||p' - p|| \leq \delta$$ where $$\delta$$ is a separation threshold defined as an input data. Note that for Gurobi and CPLEX, the quadratic constraints must have the following form : $$X^TQX + q^TX \leq b$$ where Q is a semi-definite positive matrix. Let $$\Delta = || (x_\text{max},y_\text{max}) - (x_\text{min},y_\text{min})||$$. Using $$\delta^2$$, $$\Delta^2$$ and the canonical scalar product of $$\mathbb{R}^2$$, I think we can have a valid constraint that forces the binary variables to be equal to 0 for the couples of points that are seperated by a distance greater or equal than $$\delta$$, it would look like this : $$1-u_{pp'}\geq \dfrac{\text{distance_between_p_and_p'}^2-\delta^2}{\Delta^2}$$ where $$\text{distance_between_p_and_p'}^2$$ is a term of the form "$$X^TQX$$". In that case, the inequality is is the right sense, Q is semi-definite positive : it looks OK to me. I am now looking for a way to have to complementary implication : the binary variable equal to 1 when two points are too close according to the $$\delta$$ threshold. Do you think that is possible ? Do you have any advice ? Thanks a lot ! asked 12 Dec '14, 08:59 Sycropane 21●4 accept rate: 0%
Be the first one to answer this question!
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: