2
$\begingroup$

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 !

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.