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
Sycropane |