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 !